Independent set, induced matching, and pricing: Connections and tight (subexponential time) approximation hardnesses

Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

36 Citations (Scopus)

Abstract

We present a series of almost settled inapproximability results for three fundamental problems. The first in our series is the subexponential-time inapproximability of the independent set problem, a question studied in the area of parameterized complexity. The second is the hardness of approximating the bipartite induced matching problem on bounded-degree bipartite graphs. The last in our series is the tight hardness of approximating the khypergraph pricing problem, a fundamental problem arising from the area of 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 independent set problem must run in at least 2n1-ε/r1+ε time. This nearly matches the upper bound of 2n/r [23]. It also improves some hardness results in the domain of parameterized complexity (e.g., [26], [19]). • For any k larger than some constant, there is no polynomial time min {k1-ε, n1/2-ε} -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), ̃O ( √ n) } (by Balcan and Blum [3] and an algorithm in this paper). We note an interesting fact that, in contrast to n1/2-ε hardness for polynomial-time algorithms, the k-hypergraph pricing problem admits nδ approximation for any δ > 0 in quasi-polynomial time. This puts this 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 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 induced matching number of dispersers. Then, we show that the n1/2-ε hardness of the last problem follows from nearly tight 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.

Original languageEnglish
Title of host publicationProceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013
Pages370-379
Number of pages10
DOIs
Publication statusPublished - 2013
MoE publication typeA4 Article in a conference publication
EventAnnual Symposium on Foundations of Computer Science - Berkeley, United States
Duration: 27 Oct 201329 Oct 2013
Conference number: 54

Conference

ConferenceAnnual Symposium on Foundations of Computer Science
Abbreviated titleFOCS
CountryUnited States
CityBerkeley
Period27/10/201329/10/2013

Keywords

  • Algorithmic pricing
  • Approximation algorithms
  • Subexponential-time algorithms

Fingerprint Dive into the research topics of 'Independent set, induced matching, and pricing: Connections and tight (subexponential time) approximation hardnesses'. Together they form a unique fingerprint.

Cite this