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.
Polynomial time algorithm for finding two or more vertex-disjoint cycles
algorithms;graphs;polynomial time