Hitting Selected (Odd) Cycles

Abstract

In the Subset Odd Cycle Transversal (Subset OCT) problem, the input is a graph $G$, a subset of vertices $T$ and a positive integer $k$ and the objective is to determine whether there exists a $k$-sized vertex subset that intersects every odd cycle containing a vertex from $T$. Clearly, Subset OCT is a generalization of the classic Odd Cycle Transversal problem where the objective is to determine whether there exists a $k$-sized vertex subset that intersects every odd cycle in the given graph. We remark that Subset OCT also generalizes the well known Multiway Cut problem, as well as a parity constrained variant, the Odd Multiway Cut problem. Recently, Kakimura, Kawarabayashi, and Kobayashi [Proceedings of SODA, 2012, pp. 1726--1736] proposed a fixed parameter tractable (FPT) algorithm for this problem that runs in time $f(k)mn^3$ using the theory of graph minors, where $f$ is some function, and $n$ and $m$ denote the number of vertices and edges in the graph. However, the dependence of this function on $k$ is at least triple exponential. In this paper, we give the first FPT algorithm for this problem where the exponential dependence of the running time of the algorithm on $k$ is polynomial. Our algorithm avoids the use of the theory of graph minors, is self contained, and runs in time $2^{\mathcal{O}(k^3\log k)}mn^2\log^2 n$, thus improving upon the algorithm of Kakimura and co-authors with respect to both the parameter as well as the input size. Our algorithm utilizes a recursive application of “generalized” important separators to reduce the subset version of this problem to the standard version of the problem.