Sparsification and subexponential approximation (Q1702300)

This paper studies the question of whether subexponential-time approximation algorithms can be ruled out for certain NP-complete problems, assuming the nowadays standard Exponential Time Hypothesis (ETH). The ETH conjectures that the 3-Satisfiability problem (3-SAT) cannot be solved in subexponential time; formally, there exists a positive constant \(c > 0\) such that no algorithm can solve 3-SAT in the worst case in time \(O(2^{cn})\) up to poly-logarithmic factors, and where \(n\) is the number of variables. (It is crucial to note here that the number of clauses, \(m\), does not appear in the statement of ETH.) In [J. Comput. Syst. Sci. 63, No. 4, 512--530 (2001; Zbl 1006.68052)], \textit{R. Impagliazzo} et al. showed that assuming ETH holds, its hardness also extends to many NP-complete problems other than 3-SAT, meaning that problems such as \(k\)-Set Cover, Vertex Cover, and Independent Set also do not have subexponential-time algorithms. This was achieved by their ``sparsification lemma'', which showed how to reduce a given 3-SAT instance into a subexponential number of ``sparse'' 3-SAT instances, while preserving (in a well-defined sense omitted here) the satisfiability of the original instance. Here, a sparse 3-SAT instance has at most \(O(n)\) clauses. The sparsification lemma is very powerful, and yields lovely results about the impossibility of subexponential-time algorithms for certain NP-complete problems (assuming ETH). The next natural step is hence to ask whether this subexponential-time intractability also applies to not solving such NP-complete problems exactly, but rather approximately. Here, an \(r\)-approximation algorithm (for \(0 < r < 1\)) for 3-SAT is any algorithm which outputs a solution satisfying at least \(r\) times the optimal number of simultaneously satisfiable clauses. Previously, Max Independent Set and Vertex Cover were shown to be inapproximable within any constant \(r\) in essentially subexponential time. The present paper shows how to reduce these known inapproximability results further to various other NP-complete problems, such as Min Dominating Set, Min Feedback Vertex Set, Min Set Cover, etc. The approach taken is to develop a new variant of a sparsifier known as an ``approximation-preserving sparsifier'' (note the sparsifier of Impagliazzo et al. does not preserve approximation ratios, and hence cannot be used here). The overall strategy is as follows: Assume ETH. For a problem \(P\) that we wish to show it cannot be approximated in subexponential time, apply an approximation-preserving sparsifier to Vertex Cover to output a subexponential number of new instances of Vertex Cover each of which is sparse (i.e., the number of edges scales with the number of vertices). Then, apply an approximation-preserving reduction to reduce Vertex Cover to \(P\). Note that the reason for the sparsification step to be crucial here is that most approximation-preserving reductions in the literature blow up the instance size, i.e., map an input Vertex Cover instance with \(n\) vertices to an instance of \(P\) of size \(O(n+m)\) so that a subexponential-time intractability result for Vertex Cover (with respect only to \(n\)) does not immediately carry over to \(P\).