What is the fastest known deterministic algorithm that can recognize directed graphs with a pair of vertex disjoint cycles? I know graphs with min outdegree three always have such a pair (Thomassen'83), but even so I cannot find an efficient algorithm in the general case. Does anyone know a reference for this?
$\begingroup$
$\endgroup$
2
asked Nov 10, 2016 at 19:15
-
1$\begingroup$ For undirected graph, it is NP-complete to recognize graphs with vertex set partitionable into two equal-size vertex disjoint cycles. $\endgroup$– Mohammad Al-TurkistanyNov 11, 2016 at 18:19
-
1$\begingroup$ The characterization for undirected graphs is also non-trival, due to Lovasz, and can be found e.g. here: arxiv.org/abs/1601.03791. $\endgroup$– domotorpNov 11, 2016 at 19:51
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
According to Grohe and Grüber "Parameterized approximability of the disjoint cycle problem" (ICALP 2007) there is an algorithm for finding $k$ vertex-disjoint cycles in a digraph, in time $n^{f(k)}$ for some function $f$ (polynomial for fixed $k$ but not FPT) in the section 5 of Reed, Robertson, Seymour and Thomas, "Packing directed circuits" (Combinatorica 1996) (which in turn uses theorem 3 of "The directed subgraph hemeomorphism problem" of Fortune, Hopcroft, and Wyllie.)
answered Nov 13, 2016 at 3:17
-
2$\begingroup$ Just want to add a small comment. It may be worthwhile to look at directed treewidth and the recent grid theorem of Kreutzer and Kawarabayashi which sheds some additional light on the techniques in Reed etal paper. They got around the directed grid minor theorem to prove the Erdos-Posa theorem for directed graphs but it is useful to see the high-level scheme in light of the directed grid theorem. $\endgroup$ Nov 13, 2016 at 19:21
$\begingroup$
$\endgroup$
For a strongly connected digraph $H$ and a general digraph $G$, there is an algorithm which runs in $|G|^{f (k+|H|)}$ and finds $k$ disjoint butterfly models of $H$ in $G$ if exists. For finding two disjoint cycles we have $|H|=1, k=2$. This is a direct consequence of algorithmic proof of Theorem 4.3 in
