There has been significant success in designing highly efficient algorithms for distance and shortest-path queries in recent years; many of the state-of-the-art algorithms use the hub labeling framework. In this paper, we study the approximability of the Hub Labeling problem. We prove a hardness of Ω(logn) for Hub Labeling, matching known approximation guarantees. The hardness result applies to graphs that have multiple shortest paths between some pairs of vertices. No hardness of approximation results were known previously. Then, we focus on graphs that have a unique shortest path between each pair of vertices. This is a very natural family of graphs, and much research on the Hub Labeling problem has studied such graphs. We give an O (log D) approximation algorithm for graphs of shortest-path diameter D with unique shortest paths. In particular, we get an O(loglog n) approximation for graphs of polylogarithmic diameter, while previously known algorithms gave an O(log n) approximation. Finally, we present a polynomial-time approximation scheme (PTAS) and quasi-polynomial-time algorithms for Hub Labeling on trees; additionally, we analyze a simple combinatorial heuristic for Hub Labeling on trees, proposed by Peleg in 2000. We show that this heuristic gives an approximation factor of 2.

The partial string avoidability problem, also known as partial word avoidability, is stated as follows: given a finite set of strings with possible ``holes'' (undefined symbols), determine whether there exists any two-sided infinite string containing no substrings from this set, assuming that a hole matches every symbol. The problem is known to be NP-hard and in PSPACE, and this paper establishes its PSPACE-completeness. Next, string avoidability over the binary alphabet is interpreted as a version of conjunctive normal form (CNF) satisfiability problem (SAT), with each clause having infinitely many shifted variants. Non-satisfiability of these formulas can be proved using variants of classical propositional proof systems, augmented with derivation rules for shifting constraints (such as clauses, inequalities, polynomials, etc). Two results on their proof complexity are established. First, there is a particular formula that has a short refutation in Resolution with shift, but requires classical proofs of exponential size (Resolution, Cutting Plane, Polynomial Calculus, etc.). At the same time, exponential lower bounds for shifted versions of classical proof systems are established.

The resolution complexity of the perfect matching principle was studied by Razborov [1], who developed a technique for proving its lower bounds for dense graphs. We construct a constant degree bipartite graph Gn such that the resolution complexity of the perfect matching principle for Gn is 2Ω(n) w here n is the number of vertices in Gn. This lower bound is tight up to some polynomial. Our result implies the 2Ω(n) lower bounds for the complete graph K2n + 1 and the complete bipartite graph Kn,O(n) that improves the lower bounds following from [1]. We show that for every graph G with n vertices that has no perfect matching there exists a resolution refutation of perfect matching principle for G of size O(n22n). Thus our lower bounds match upper bounds up to a multiplicative constant in the exponent. Our results also imply the well-known exponential lower bounds on the resolution complexity of the pigeonhole principle, the functional pigeonhole principle and the pigeonhole principle over a graph. We also prove the following corollary. For every natural number d, for every n large enough, for every function h : {1, 2, . . . , n} → {1, 2, . . . , d}, we construct a graph with n vertices that has the following properties. There exists a constant D such that the degree of the i-th vertex is at least h(i) and at most D, and it is impossible to make all degrees equal to h(i) by removing the graph’s edges. Moreover, any proof of this statement in the resolution proof system has size 2Ω(n). This result implies well-known exponential lower bounds on the Tseitin formulas as well as new results: for example, the same property of a complete graph. Preliminary version of this paper appeared in proceedings of CSR-2015 [2].