13
$\begingroup$

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?

$\endgroup$
  • 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-Turkistany Nov 11 '16 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$ – domotorp Nov 11 '16 at 19:51
9
$\begingroup$

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.)

$\endgroup$
  • 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$ – Chandra Chekuri Nov 13 '16 at 19:21
2
$\begingroup$

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

https://arxiv.org/abs/1603.02504

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.