Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
share
We generalize the monotone local search approach of Fomin, Gaspers, Lokshtanov and Saurabh [J.ACM 2019], by establishing a connection between parameterized approximation and exponential-time approximation algorithms for monotone subset minimization problems. In a monotone subset minimization problem the input implicitly describes a non-empty set family over a universe of size n which is closed under taking supersets. The task is to find a minimum cardinality set in this family. Broadly speaking, we use approximate monotone local search to show that a parameterized α-approximation algorithm that runs in c^k · n^O(1) time, where k is the solution size, can be used to derive an α-approximation randomized algorithm that runs in d^n · n^O(1) time, where d is the unique value in d ∈ (1,1+c-1/α) such that 𝒟(1/αd-1/c-1)=ln c/α and 𝒟(a b) is the Kullback-Leibler divergence. This running time matches that of Fomin et al. for α=1, and is strictly better when α >1, for any c > 1. Furthermore, we also show that this result can be derandomized at the expense of a sub-exponential multiplicative factor in the running time. We demonstrate the potential of approximate monotone local search by deriving new and faster exponential approximation algorithms for Vertex Cover, 3-Hitting Set, Directed Feedback Vertex Set, Directed Subset Feedback Vertex Set, Directed Odd Cycle Transversal and Undirected Multicut. For instance, we get a 1.1-approximation algorithm for Vertex Cover with running time 1.114^n · n^O(1), improving upon the previously best known 1.1-approximation running in time 1.127^n · n^O(1) by Bourgeois et al. [DAM 2011].
READ FULL TEXT