Archive for July, 2013

Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses

July 4, 2013 at 7:11 am · Filed under Approximation, FOCS, Uncategorized

We present a series of almost settled inapproximability results for three fundamental problems. The first in our series is the {\em subexponential-time} inapproximability of the {\em maximum independent set} problem, a question studied in the area of {\em parameterized complexity}. The second is the hardness of approximating the {\em maximum induced matching} on bounded-degree bipartite graphs. The last in our series is the tight hardness of approximating the {\em k-hypergraph pricing} problem, a fundamental problem arising from the area of {\em algorithmic game theory}. In particular, assuming the Exponential Time Hypothesis, our two main results are:

  • For any r larger than some constant, any r-approximation algorithm for the maximum independent set problem must run in time at least 2^{n^{1-\epsilon}/r^{1+\epsilon}}. This nearly matches the upper bound of 2^{n/r} [Cygan et al:  Manuscript 2008]. It also improves some hardness results in the domain of parameterized complexity (e.g. [Escoffier et al: Manuscript 2012] and [Chitnis et al: Manuscript 2013]).
  • For any k larger than some constant, there is no polynomial time \min \{k^{1-\epsilon}, n^{1/2-\epsilon}\}-approximation algorithm for the k-hypergraph pricing problem , where n is the number of vertices in an input graph. This almost matches the upper bound of  \min \{O(k), \tilde O(\sqrt{n})\}  (by Balcan and Blum in [Balcan and Blum: Theory of Computing 2007] and an algorithm in this paper).

We note an interesting fact that, in contrast to n^{1/2-\epsilon} hardness, the k-hypergraph pricing problem admits n^{\delta} approximation for any \delta >0 in quasi-polynomial time. This puts pricing problem in a rare approximability class in which approximability thresholds can be improved significantly by allowing algorithms to run in quasi-polynomial time.
The proofs of our hardness results rely on several unexpectedly tight connections between the three problems. First, we establish a connection between the first and second problems by proving a new graph-theoretic property related to an {\em induced matching number} of dispersers. Then, we show that the n^{1/2-\epsilon} hardness of the last problem follows from nearly tight {\em subexponential time} inapproximability of the first problem, illustrating a rare application of the second type of inapproximability result to the first one. Finally, to prove the subexponential-time inapproximability of the first problem, we construct a new PCP with several properties; it is sparse and has nearly-linear size, large degree, and small free-bit complexity. Our PCP requires no ground-breaking ideas but rather a very careful assembly of the existing ingredients in the PCP literature.

Leave a Comment

Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization

July 4, 2013 at 7:03 am · Filed under FOCS, Running Time

Abstract

We study dynamic (1+\epsilon)-approximation algorithms for the all-pairs shortest paths problem in unweighted undirected n-node m-edge graphs under edge deletions. The fastest algorithm for this problem is a randomized algorithm with a total update time of \tilde O(mn) and constant query time by Roditty and Zwick (FOCS 2004). The fastest deterministic algorithm is from a 1981 paper by Even and Shiloach (JACM 1981); it has a total update time of O(mn^2) and constant query time. We improve these results as follows:

(1) We present an algorithm with a total update time of \tilde O(n^{5/2}) and constant query time that has an additive error of two in addition to the (1+\epsilon) multiplicative error. This beats the previous \tilde O(mn) time when m=\Omega(n^{3/2}). Note that the additive error is unavoidable since, even in the  static case, an O(n^{3-\delta})-time (a so-called truly subcubic) combinatorial algorithm with (1+\epsilon) multiplicative error cannot have an additive error less than 2-\epsilon, unless we make a major breakthrough for Boolean matrix multiplication (Dor, Halperin and Zwick FOCS 1996) and many other long-standing problems (Vassilevska Williams and Williams FOCS 2010). The algorithm can also be turned into a (2+\epsilon)-approximation algorithm (without an additive error) with the same time guarantees, improving the recent (3+\epsilon)-approximation algorithm with \tilde O(n^{5/2+O(1/\sqrt{\log n})}) running time of Bernstein and Roditty (SODA 2011) in terms of both approximation and time guarantees.

(2) We present a deterministic algorithm with a total update time of \tilde O(mn) and a query time of O(\log\log n). The algorithm has a multiplicative error of (1+\epsilon) and gives the first improved deterministic algorithm since 1981. It also answers an open question raised by Bernstein in his STOC 2013 paper.

In order to achieve our results, we introduce two new techniques: (1) A monotone Even-Shiloach tree algorithm which maintains a bounded-distance shortest-paths tree on a certain type of emulator called locally persevering emulator.  (2) A derandomization technique based on moving Even-Shiloach trees as a way to derandomize the standard random set argument. These techniques might be of independent interest.

Leave a Comment