Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Background: I'm experimenting with programs that create non-planar undirected graphs from three-dimensional meshes. A graph created by program A is not necessarily isomorphic to one created by program B. However the number of cycles should be identical, else something went wrong (a small triangle was missed or seam between two triangles was accidentally filled).

Now I've been looking for a way to compute the number of cycles in these graphs. I found a few simple algorithms which run in non-polynomial time. However I cannot find any references that state that there is no polynomial time solution. Note that I do not care about the actual cycles, I only care about the number of cycles. Would that give me some opportunities to take short-cuts?

If this is totally impossible (which I can image, this could be closely related to the graph-isomorphism problem) are there any other properties of graphs that say something about the layout-of the graph but do not care about an extra node if it only has one incoming and one outgoing edge. To illustrate I would like the following two graphs to be equal in the terms of this property.

Two graphs

My definition of reasonable here is that it can be computed within 15 minute on a modern computer, for a graph with 10.000 edges. I imagine even some non-polynomial solutions that use dynamic programming should be able to achieve this.

share|improve this question

1 Answer 1

You probably want to use Johnson's algorithm. This finds all the cycles in a directed graph in $O((n+e)(c+1))$ time, where $n$ is the number of vertices, $e$ is the number of edges, and $c$ is the number of cycles. Of course you can use this algorithm to find cycles in undirected graphs by creating a directed version of your undirected graph $G$ with edges $u\rightarrow v$ and $v \rightarrow u$ for each $(u,v) \in E(G)$, running the algorithm on the directed graph, and removing the duplicate cycles.

Unfortunately, if your graph has many cycles, the algorithm is still exponential, but I believe it is the best known at this time.

Since the paper may not be available to you, here is a link to the NetworkX implementation of that algorithm. Also, you might be interested in this more modern paper that describes an implementation of Johnson's algorithm that also allows for multiple arcs and loops.

share|improve this answer
    
Is a better solution available if I limit the problem to finding all the 'shortest cycles'? (both graphs above would only have 2 cycles then instead of 3) –  Roy T. Jul 30 at 10:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.