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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: