# Pair of vertex disjoint cycles in a directed graph

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?

• For undirected graph, it is NP-complete to recognize graphs with vertex set partitionable into two equal-size vertex disjoint cycles. – Mohammad Al-Turkistany Nov 11 '16 at 18:19
• The characterization for undirected graphs is also non-trival, due to Lovasz, and can be found e.g. here: arxiv.org/abs/1601.03791. – domotorp Nov 11 '16 at 19:51

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