Optimally Repurposing Existing Algorithms to Obtain Exponential-Time Approximations
Barış Can Esmer, Ariel Kulik, Dániel Marx, Daniel Neuen, Roohani Sharma · Society for Industrial and Applied Mathematics eBooks · 2024
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 ck · nO(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 dn · nO(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: