Parameterized Complexity and Approximability of Directed Odd Cycle Transversal

摘要

A directed odd cycle transversal of a directed graph (digraph) $D$ is avertex set $S$ that intersects every odd directed cycle of $D$. In the DirectedOdd Cycle Transversal (DOCT) problem, the input consists of a digraph $D$ andan integer $k$. The objective is to determine whether there exists a directedodd cycle transversal of $D$ of size at most $k$. In this paper, we settle the parameterized complexity of DOCT whenparameterized by the solution size $k$ by showing that DOCT does not admit analgorithm with running time $f(k)n^{O(1)}$ unless FPT = W[1]. On the positiveside, we give a factor $2$ fixed parameter tractable (FPT) approximationalgorithm for the problem. More precisely, our algorithm takes as input $D$ and$k$, runs in time $2^{O(k^2)}n^{O(1)}$, and either concludes that $D$ does nothave a directed odd cycle transversal of size at most $k$, or produces asolution of size at most $2k$. Finally, we provide evidence that there exists$epsilon > 0$ such that DOCT does not admit a factor $(1+epsilon)$FPT-approximation algorithm.