# Longest circuit in a directed graph

I have a very large directed graph (1M nodes) I am wondering what is the best algorithm for finding the longest (most number of nodes) cycle in the graph?

• The longest cycle (no repeated nodes), or the longest circuit (which may in general repeat nodes, even if you do not double-count them)? If the latter, we will also have to add the restriction that it does not also repeat edges, in order to obtain finite results. Aug 26 '11 at 11:36
• @Niel de Beaudrap I don't believe there is standard terminology for this. Aug 26 '11 at 18:55
• @Tyson Williams: depending on what Mark is asking about, there may be. For instance, in graph theory (among English speakers) one does distinguish between cycles and circuits; and the distinction is precisely whether or not a node is allowed to be revisited (no for cycles, yes for circuits). Aug 26 '11 at 19:03
• @Niel de Beaudrap This doesn't have anything to do with OP's question. I am just saying that cycle (no repeated nodes) and circuit (allows repeated nodes) is not standard terminology for these concepts because there is no standard terminology. See en.wikipedia.org/wiki/Cycle_(graph_theory) Aug 27 '11 at 0:05
• Assuming that one wants a cycle in which nodes are not repeated, the problem is of course NP-Hard via a reduction from the Hamiltonian cycle problem. Finding an effective heuristic on a large graph requires a good understanding of the problem instances. Aug 28 '11 at 19:14

One million nodes is far too much for any exact method that I know. This being said, I expect your graph does not have a very large number of edges, so the best is to begin by applying repeatedly this algorithm :

If you have a vertex in your graph that has not outgoing edge, or that has no incoming edge, remove it from your graph as no cycle can go through it. Take care, as removing such vertices can lead to remove other vertices that had edges in both direction before !

This should reduce dramatically the size of your graph (look at what is called "topological sort"). Once this is done, you can compute the different strongly connected componets, as your cycle is included in one of them. Then, you can do the computations separatedly. Perhaps the splitting of your graph will have created new vertices that you can remove.

Iterate through these two algorithms until you can do no other operation in your graph. When it is done, come back here and ask your question again giving the new number of vertices.

When you do so, do not count the number of vertices having exactly one incoming edge and one outgoing edge. They do not change the complexity of the problem.

If after all this your graph is still 1M vertices large, it begins to really be desperate :-)

Nathann

• @Mark: especially if what you would like is the largest cycle — as opposed to the largest circuit — Nathan's remarks about decreasing the size as much as possible, and determining the strongly connected components, are quite good advice. Even if you discover that you have to do brute-force searching in two large strongly connected components of size 500 thousand, this (while still labor-intensive) is dramatically better than brute-force searching in a single network of 1 million. Aug 26 '11 at 16:39