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

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.

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.