Optimally Repurposing Existing Algorithms to Obtain Exponential-Time Approximations

The goal of this paper is to understand how exponential-time approximation algorithms can be obtained from existing polynomial-time approximation algorithms, existing parameterized exact algorithms, and existing parameterized approximation algorithms. More formally, we consider a monotone subset minimization problem over a universe of size n (e.g., Vertex Cover or Feedback Vertex Set). We have access to an algorithm that finds an α-approximate solution in time c k • n O(1) if a solution of size k exists (and more generally, an extension algorithm that can approximate in a similar way if a set can be extended to a solution with k further elements). Our goal is to obtain a d n • n O(1) time β-approximation algorithm for the problem with d as small as possible. That is, for every fixed α, c, β ≥ 1, we would like to determine the smallest possible d that can be achieved in a model where our problem-specific knowledge is limited to checking the feasibility of a solution and invoking the α-approximate extension algorithm. Our results completely resolve this question:

The author is part of Saarbrücken Graduate School of Computer Science, Germany.