Enumerating All Minimal Directed Cycles Of A Directed Graph

Question

Hello!

I have a directed graph and my problem is to enumerate all the minimal (cycles that cannot be constructed as the union of other cycles) directed cycles of this graph. This is different from what the Tarjan algorithm outputs. For instance, for the directed graph at this wikipedia page, I would like to get c <-> d and d <-> h as two separated directed cycles.

I don't if this problem is polynomial or not. I ran over a paper "Enumerating Minimal Dicuts and Strongly Connected Subgraphs" that seems to conclude that this problem is incremental polynomial (I don't know what it means), but I am unable to extract an algorithm for this article. I am also not sure if a minimal strongly connected component is equivalent to a minimal cycle as I define it.

Does someone knows the answer to this problem?

Thanks in advance!!!

Answer 1

If we are looking for the shortest path cycle, it seems easy enough.

• Just do a breadth first search on all nodes searching for the shortest path from a node to itself.
• if you find no path, you can remove this node it is in no cycle
• if you find a path, you have found one of your minimal cycles (as we looked for shortest path, we can ensure this cycle can't be the union of two shorter cycles).
  • Collapse all nodes in it in one big new node and adapt edges as necessary.

• Go on until there is no node any-more.

• When You you have treated all nodes (vertexes) you have the minimal cycles you where looking for... but there is a trick.

If a cycle is expressed using only nodes from the initial set you can keep it "as is". But you have to translate "big nodes" to paths (common edges between cycles) and every big nodes may be replaced by several such path (at least 2 for a big node of level-1, that is that does not contains big nodes itself). The cycles found are constructed in such a way that you can choose any path and still get a minimal cycle set (no cycle can be get doing the union of two others), but there is several possible such sets. You can add a constraint to always take a shortest path when selecting a path in a big node, but there still can be paths of the same length. So the solution of this problem is clearly enough not unique.

With this naive approach complexity would be O(V.(E+V)) where V is the number of vertexes and E the number of edges. O(E+V) comes from breadth first and at worst you have to perform a BFS V times. Hence it is definitely polynomial of better. I believe what I described is really O(log(V).(E+V)) in the average case, but I didn't prooved it yet (if it's true).

Answer 2

We're looking for all simple cycles, not just the shortest or cheapest. (If simple is the right term-- I mean cycles that do not self-intersect.)

Here's a breadth-first algorithm that should do the job:
Number the nodes. Place a salesman on every node and begin the operation: If a salesman has a choice of which edge to take, he copies himself and goes all possible ways. When he arrives at a node, if it has a lower number than the one he started on he dies, and if it's one he's visited before he records that cycle and dies. Remove the redundant cycles from the list.

I'm not sure of the complexity of this, but it looks like O(EV^2).

EDIT:
Now that I think of it, you can probably get to O(EV) by starting with one salesman on the lowest numbered node. When all his descendents are dead, start again with a salesman on the lowest numbered node that has not yet been visited. Repeat until all nodes have been visited.

Answer 3

Maybe an enumeration of INDEPENDENT cycles will help?

I'd try the following.

1. First, in order to find what vertexes participate in cycles, do a transitive closure. It's a O(V^3) algorithm.
2. Remove all the other vertexes.
3. Now, there exists a full independent cycle coverage of the remaining graph (this is the weak point of my idea, I can't prove that the cycles will be independent)
4. The solution for it is - "maximal pair matching in bipartitive graph" algorithm.

4.1. Turn each vertex v in your graph (G) into 2 (v1 and v2), place each in different parts of bipartitive graph (G2).

4.2. For each edge e(v,u) in G, add an edge from 1st part of G2 to 2nd - e(v1,u2).

4.3. Find a maximal pair matching in G2. It's a subset of G2 edges.

5 That subset corresponds to a maximal (full) set of independent loops in G.