A sparsification of a problem maps the problem to a set of similar problems, each of which has its parameters bounded by some fixed number. For example, in the case of a graph-based problem, the degree might be one parameter. The solutions of these sparser problems should then map to a solution of the original problem.
The authors illustrate the notion of sparsification using MIN VERTEX COVER as an example. The paper’s main idea is to refine the notion of a sparsification to require that the solutions to the set of problems give rise to a solution to the original problem that approximates the optimal value for a solution to the original problem. Typically the problems studied are MIN DOMINATING SET, MIN FEEDBACK VERTEX SET, MIN SET COVER, and MIN FEEDBACK ARC SET, among others. This paper uses the notion of an approximation preserving sparsification, defined in detail by the authors, to show that, assuming the exponential time hypothesis (ETH), the problems listed above cannot be approximately solved to within a specified approximation by algorithms having explicitly given exponential time constraints determined by the ETH.
The paper contains detailed proofs of the results, and a useful appendix includes definitions of all the problems discussed. The paper will be of interest to people interested in the question of computing optimal solutions to any of the problems referred to here.