COMPUTER SCIENCE COLLOQUIUM

The complexity of finding disjoint cycles and dicycles in a digraph.

Alessandro Maddaloni and Sven Simonsen Department of Mathematics and Computer Science University of Southern Denmark, Denmark

Wednesday, 22 June, 2011 at 14:15 U49

ABSTRACT

Consider the following problem: Given a directed graph $D$, does it have two vertex disjoint cycles? If we ask for two undirected cycles then it has been proven by Lovazs and Dirac that the problem can be decided in polynomial time. Likewise if we ask for two directed cycles then it is again polynomially decidable, by a result of McCuaig.

So we considered a mixed problem, where only one of the cycles has to be directed. Our co-authors Bang and Kriesell proved that one can decide the problem in polynomial time if $D$ is strongly connected.

We will look at the problem for general digraphs and find, perhaps surprisingly, that it is $\mathcal{NP}$-complete, but it turns out that the problem is still polynomial in many interesting cases: We give a complete characterization for the complexity of the problem in terms of the cycle transversal number $\tau (D)$ of $D$, i.e. the smallest cardinality of a set $T$ of vertices in $D$ such that $D-T$ is acyclic.

Host:

---

SDU HOME | IMADA HOME | Previous Page

---

Daniel Merkle