<p>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 </p>

<p><a href="https://arxiv.org/abs/1603.02504" rel="nofollow noreferrer">https://arxiv.org/abs/1603.02504</a></p>

CC BY-SA 3.0
2016-11-14T08:06:49.183Z
2016-11-14T08:11:59.110Z
2016-11-14T08:11:59.110Z
Saeed
<p>According to Grohe and Grüber "<a href="http://www.cs.technion.ac.il/~hadas/Seminar/Papers/Disjoint_cycles_full.pdf" rel="nofollow noreferrer">Parameterized approximability of the disjoint cycle problem</a>" (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, "<a href="http://dx.doi.org/10.1007/BF01271272" rel="nofollow noreferrer">Packing directed circuits</a>" (Combinatorica 1996) (which in turn uses theorem 3 of "<a href="http://dx.doi.org/10.1016/0304-3975(80)90009-2" rel="nofollow noreferrer">The directed subgraph hemeomorphism problem</a>" of Fortune, Hopcroft, and Wyllie.)</p>

CC BY-SA 3.0
2016-11-13T19:21:31.550Z
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.
Chandra Chekuri
CC BY-SA 3.0
2016-11-13T03:17:45.030Z
2016-11-13T19:37:18.000Z
2016-11-13T19:37:18.000Z
David Eppstein
<p>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 (<a href="http://link.springer.com/article/10.1007/BF02579195" rel="nofollow noreferrer">Thomassen'83</a>), but even so I cannot find an efficient algorithm in the general case. Does anyone know a reference for this?</p>

CC BY-SA 3.0
2016-11-11T18:19:15.863Z
For undirected graph, it is NP-complete to recognize graphs with vertex set  partitionable into two equal-size vertex disjoint cycles.
Mohammad Al-Turkistany
CC BY-SA 3.0
2016-11-11T19:51:55.370Z
The characterization for undirected graphs is also non-trival, due to Lovasz, and can be found e.g. here: https://arxiv.org/abs/1601.03791.
domotorp
<reference-request>
Pair of vertex disjoint cycles in a directed graph
Andreas Björklund
# Pair of vertex disjoint cycles in a directed graph

(Asked by: username_0 on 2016-11-10)

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](http://link.springer.com/article/10.1007/BF02579195)), but even so I cannot find an efficient algorithm in the general case. Does anyone know a reference for this?

**Tags:** reference-request
> **Comments:**
> **username_1**: For undirected graph, it is NP-complete to recognize graphs with vertex set  partitionable into two equal-size vertex disjoint cycles.  
> **username_2**: The characterization for undirected graphs is also non-trival, due to Lovasz, and can be found e.g. here: https://arxiv.org/abs/1601.03791.  

---

## 2 answers

### Answer by username_4 on 2016-11-13. Score: 9 | Accepted answer

According to Grohe and Grüber "[Parameterized approximability of the disjoint cycle problem](http://www.cs.technion.ac.il/~hadas/Seminar/Papers/Disjoint_cycles_full.pdf)" (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](http://dx.doi.org/10.1007/BF01271272)" (Combinatorica 1996) (which in turn uses theorem 3 of "[The directed subgraph hemeomorphism problem](http://dx.doi.org/10.1016/0304-3975(80)90009-2)" of Fortune, Hopcroft, and Wyllie.)

> **Comments:**
> **username_5**: 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.  

---

### Answer by username_3 on 2016-11-14. Score: 2

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>


---

