5
$\begingroup$

The cycle detection problem for a directed graph has well-known polynomial time solutions, graph traversal algorithms such as Dijkstra algorithm can be used to find whether or not a cycle exists in a graph.

The difficulty however comes when we are required to find in polynomial time whether 2 vertex disjoint cycles exist in an arbitrary graph. Is there such a polynomial time algorithm which finds whether 2 vertex disjoint cycles exist in an arbitrary graph?

By vertex disjoint cycles, I mean cycles which do not share a common vertex.

$\endgroup$
  • 1
    $\begingroup$ Dijkstra is overkill for cycle detection; a simple graph traversal (e.g. BFS or DFS) is enough. In particular, Dijkstra is not (only) a graph traversal algorithm. $\endgroup$ – Raphael Apr 9 '15 at 19:54
5
$\begingroup$

The structure of graphs without two vertex-disjoint cycles is well understood (see for example Bollobás, Extremal graph theory), having been researched in 1965 by Dirac and the 17-year old Lovász (separately).

Theorem 1. Suppose that $G$ has minimum degree at least $3$. Then $G$ has no two vertex-disjoint cycles if and only if one of the following holds:

  1. $G \setminus \{v\}$ is a forest for some vertex $v$.

  2. $G$ is a wheel (a cycle plus a vertex connected to all vertices in the cycle).

  3. $G$ is $K_5$, the clique on 5 vertices.

  4. $G \setminus \{v,u,w\}$ is an independent set for some three vertices $v,u,w$.

Theorem 2. A graph $G$ has no two vertex-disjoint cycles if and only if either $G \setminus \{v\}$ is a forest for some $v$, or $G$ is obtained from one of the graphs $H$ in Theorem 1 by subdividing edges, adding a forest, and possibly connecting each tree in the forest by a unique path to $H$.

Theorem 1 can clearly be implemented algorithmically in polynomial time. In order to implement Theorem 2, we need to undo the subdivision and remove the forest and its attaching paths. We can identify the forest by removing isolated trees and identifying paths leading to trees. We can then undo the subdivision by compressing paths, reducing to the case of Theorem 1. It seems that everything can be implemented in polynomial time.

$\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.