Sparsification and subexponential approximation

DOI10.1007/S00236-016-0281-2MaRDI QIDQ1702300zbMATH OpenOpenAlexFDO

Authors Édouard Bonnet, Vangelis Th. Paschos

Publication date 28 February 2018

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.2843

zbMATH Keywords

approximation preserving sparsifierexponential time hypothesisinapproximabilitymin dominating setmin feedback vertex setmin set coversparsificationvertex cover

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Abstract: Instance sparsification is well-known in the world of exact computation since it is very closely linked to the Exponential Time Hypothesis. In this paper, we extend the concept of sparsification in order to capture subexponential time approximation. We develop a new tool for inapproximability, called approximation preserving sparsification and use it in order to get strong inapproximability results in subexponential time for several fundamental optimization problems as Max Independent Set, Min Dominating Set, Min Feedback Vertex Set, and Min Set Cover.

Review text

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\).

Recommendations

• Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis
• On problems as hard as CNF-SAT
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• Sub-exponential approximation schemes for CSPs: from dense to almost sparse
• New tools and connections for exponential-time approximation

Cites work

• An exponential time 2-approximation algorithm for bandwidth
• Approximating the minimum maximal independence number
• Approximation algorithms for combinatorial problems
• Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
• Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
• Exact and approximate bandwidth
• Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
• scientific article; zbMATH DE number 1305522 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Lower bounds based on the exponential time hypothesis
• On Approximate Solutions for Combinatorial Optimization Problems
• On approximating the minimum independent dominating set
• On approximation algorithms for the minimum satisfiability problem
• On Parameterized Approximability
• Optimization, approximation, and complexity classes
• Parameterized Approximation Problems
• Proof verification and the hardness of approximation problems
• Reducibility among combinatorial problems
• Sparsification and subexponential approximation
• The PCP theorem by gap amplification
• Towards strong nonapproximability results in the Lovász-Schrijver hierarchy
• Two-query PCP with subconstant error
• Which problems have strongly exponential complexity?

Cited in

(13)

• Sparsification and subexponential approximation
• Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
• A primal-dual approximation algorithm for \textsc{minsat}
• New tools and connections for exponential-time approximation
• Maximum minimal vertex cover parameterized by vertex cover
• Maximum satisfiability and subexponential time
• Better approximations for tree sparsity in nearly-linear time
• Maximum minimal vertex cover parameterized by vertex cover
• Sub-exponential approximation schemes for CSPs: from dense to almost sparse
• The exponential time hypothesis and the parameterized clique problem
• The Usefulness of Sparsifiable Inputs: How to Avoid Subexponential iO
• Approximation Bounds for Sparse Programs
• Sparse Compression of Expected Solution Operators

This page was built for publication: Sparsification and subexponential approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1702300)