Directed subset feedback vertex set is fixed-parameter tractable

DOI10.1145/2700209MaRDI QIDQ4962189zbMATH OpenOpenAlexFDO

Authors Rajesh Chitnis, Marek Cygan, Mohammataghi Hajiaghayi, Dániel Marx

Publication date 30 October 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1205.1271, http://eprints.sztaki.hu/8572/

directed graphs important separators parameterized algorithms subset feedback vertex set

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: 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 a general family of transversal problems. Moreover, we modify the probability distribution used in the technique to achieve better running time; in particular, this gives an improvement from

2^{2^{O (k)}}

to

2^{O (k^{2})}

in the parameter dependence of the Directed Multiway Cut algorithm of Chitnis et al. (SODA '12).

Recommendations

Cited in

(34)

This page was built for publication: Directed subset feedback vertex set is fixed-parameter tractable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4962189)