2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Niel de Beaudrap Aug 26 '11 at 11:36
  • $\begingroup$ @Niel de Beaudrap I don't believe there is standard terminology for this. $\endgroup$ – Tyson Williams Aug 26 '11 at 18:55
  • 1
    $\begingroup$ @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). $\endgroup$ – Niel de Beaudrap Aug 26 '11 at 19:03
  • 1
    $\begingroup$ @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) $\endgroup$ – Tyson Williams Aug 27 '11 at 0:05
  • 1
    $\begingroup$ 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. $\endgroup$ – Chandra Chekuri Aug 28 '11 at 19:14
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ @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. $\endgroup$ – Niel de Beaudrap Aug 26 '11 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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