Can I read Directed Subset Feedback Vertex Set is Fixed-Parameter Tractable on EtoBox?

Directed Subset Feedback Vertex Set is Fixed-Parameter Tractable by Chitnis, Rajesh; Cygan, Marek; Hajiaghayi, MohammadTaghi; Marx, Dániel is a scholarly article available to read on EtoBox.

What is Directed Subset Feedback Vertex Set is Fixed-Parameter Tractable about?

Given a graph $G$ and an integer $k$, the Feedback Vertex Set (FVS) problem asks if there is a vertex set $T$ of size at most $k$ that hits all cycles in the graph. The fixed-parameter tractability status of FVS in directed graphs was a long-standing open problem until Chen et al. (STOC '08) showed that it is FPT by giving a $4^{k}k!n^{O(1)}$ time algorithm. In the subset versions of this problems, we are given an additional subset $S$ of vertices (resp., edges) and we want to hit all cycles passing through a vertex of $S$ (resp. an edge of $S$). Recently, the Subset Feedback Vertex Set in undirected graphs was shown to be FPT by Cygan et al. (ICALP '11) and independently by Kakimura et al. (SODA '12). We generalize the result of Chen et al. (STOC '08) by showing that Subset Feedback Vertex Set in directed graphs can be solved in time $2^{O(k^3)}n^{O(1)}$. By our result, we complete the picture for feedback vertex set problems and their subset versions in undirected and directed graphs. Besides proving the fixed-parameter tractability of Directed Subset Feedback Vertex Set, we reformulate the random sampling of important separators technique in an abstract way that can be used for

Author

Chitnis, Rajesh; Cygan, Marek; Hajiaghayi, MohammadTaghi; Marx, Dániel

Published

2012

Language

EN