FPT-approximation for FPT Problems

Over the past decade, many results have focused on the design of parameterized approximation algorithms for W[1]-hard problems. However, there are fundamental problems within the class FPT for which the best known algorithms have seen no progress over the course of the decade; some of them have even been proved not to admit algorithms that run in time 2 O(k) n O(1) under the Exponential Time Hypothesis (ETH) or (c -) k n O(1) under the Strong ETH (SETH). In this paper, we expand the study of FPT-approximation and initiate a systematic study of FPT-approximation for problems that are FPT. We design FPT-approximation algorithms for problems that are FPT, with running times that are significantly faster than the corresponding best known FPT-algorithm, and while achieving approximation ratios that are significantly better than what is possible in polynomial time.

• We present a general scheme to design 2 O(k) n O(1) -time 2-approximation algorithms for cut problems.

In particular, we exemplify it for Directed Feedback Vertex Set, Directed Subset Feedback Vertex Set, Directed Odd Cycle Transversal and Undirected Multicut.

• Further, we extend our scheme to obtain FPT-time O(1)-approximation algorithms for weighted cut problems, where the objective is to obtain a solution of size at most k and of minimum weight. Here, we present two approaches. The first approach achieves 2 O(k) n O(1) -time constant-factor approximation, which we exemplify for all problems mentioned in the first bullet. The other leads to an FPT-approximation Scheme (FPT-AS) for Weighted Directed Feedback Vertex Set.

• Additionally, we present a combinatorial lemma that yields a partition of the vertex set of a graph to roughly equal sized sets so that the removal of each set reduces its treewidth substantially, which may be of independent interest. For several graph problems, use this lemma to design c w n O(1) -time (1 + )approximation algorithms that are faster than known SETH lower bounds, where w is the treewidth of the input graph. Examples of such problems include Vertex Cover, Component Order Connectivity, Bounded-Degree Vertex Deletion and F-Packing for any family F of bounded sized graphs.

• Lastly, we present a general reduction of problems parameterized by treewidth to their versions parameterized by solution size. Combined with our first scheme, we exemplify it to obtain c w n O(1) -time bi-criteria approximation algorithms for all problems mentioned in the first bullet.