How to find the number of cycles and set of nodes in each cycle in an undirected, connected and loopless graph?

876 Views Asked by At

This question could be repetetive. I tried to look up for some posts, most of them are to check whether a graph contains a cycle or not. Assume there is no multiple edge.

My problem is I need to find all the cycles in the graph, and also be able to get the list of nodes that belong to the cycles. So is there a sufficient way to achieve this? Graph is undirected, connected and loopless.

Edited 1: The graph I am working on is defined here: Define A Graph - Tree Graph With "Cycles" as Nodes

Generally, the graph consists of some "simple cycles" that have disjoint subset of vertices of the graph. If there is an algorithm to apply for this type of graph, it is fine enough. Efficiency can be ignored here.

1

There are 1 best solutions below

1
On

In general, no. As Casteels stated in the comment, even the Hamiltonian cycle problem is NP-complete. All cycles would be impossible even- there could be exponentially many and even listing them is superpolynomial then!

But for your graph: As far as I understand, you are working with a graph that has cycles with disjoint vertices that we contract and obtain a tree. In this case, you can use that there are $|V|-1$ edges in a tree with $|V|$ vertices. Assume you find cycles and contract them consecutively. Each time you replace $k_i$ edges and $k_i$ vertices with one vertex, so $|E|-|V|$ drops by one. Let's say you do this $j$ times and obtain a tree (i.e. there are $j$ vertices). You have $1=|E|-|V|-j$. Hence you have $|E|-|V|-1$ cycles in that very special case.

To find the cycles: In efficiency is no issue, brute force is always a solution (a very bad one here). Otherwise a depth-first search should do the trick - as soon as you arrive at an already visited node, you can backtrack until you reach the node from the other way around. Since every vertex lies in at most one cycle, backtracking should not exceed linear time in total. Then you can contract the cycle to proceed if you want to make it simpler for the future, which would again be linear time in total. Also here, you use that the cycles are vertex-disjoint.