3
$\begingroup$

What's an easy-to-program way of listing all 6-cycles in a directed graph? I've done some reading on the general case of even cycles, but it's rather complicated. I found a really neat approach for 4-cycles, in this post, and I was wondering if there's something similar for 6-cycles.

My graph isn't that big (maybe a few hundred nodes) so I'm not too worried about computation time.

$\endgroup$
3
  • $\begingroup$ 1. "Best" is subjective. "Best" by what metric? Lowest asymptotic running time? Easiest to program? Smallest memory complexity? Something else? Please edit your question to clarify -- this site is for objectively evaluable questions & answers. 2. What's the best you've come up with so far, for this problem? Please show us in the question. There's little point in us showing you an answer that you already know of, so please save us from that by telling us the best algorithm you already know of. 3. Do you mean simple cycles (with no repeated vertex)? It'd help to state that explicitly. $\endgroup$
    – D.W.
    Aug 12, 2015 at 0:56
  • $\begingroup$ Have you looked at cstheory.stackexchange.com/q/19508/5038? $\endgroup$
    – D.W.
    Aug 12, 2015 at 1:04
  • 1
    $\begingroup$ You might be interested in Monien, Burkhard. "How to find long paths efficiently." North-Holland Mathematics Studies 109 (1985): 239-254.; the work of Alon et al. improves on these results. I guess you'll have to decide whether or not this is easier than the methods of Alon et al. $\endgroup$
    – Juho
    Aug 12, 2015 at 7:32

1 Answer 1

2
$\begingroup$

The easiest-to-program method will probably be a straightforward for-loop. In particular, for each combination of six vertices $v_1,v_2,\dots,v_6 \in V$, check whether the following conditions all hold:

  • the $v_1,v_2,\dots,v_6$ are all distinct
  • $(v_1,v_2) \in E$ and $(v_2,v_3) \in E$ and ... and $(v_5,v_6) \in E$ and $(v_6,v_1) \in E$.

If all the conditions hold, then you've found a cycle. Output it. Repeat for each possible combination of vertices.

The running time of this method is $\Theta(|V|^6)$. It is easy to see that in the worst case there can be $\Theta(|V|^6)$ different cycles (consider a complete graph), so any algorithm will have to take at least this long on some graphs.


You can also get a very easy-to-program algorithm with running time $\Theta(|E|^3)$. Enumerate all triples of edges $(v_1,v_2), (v_3,v_4), (v_5,v_6) \in E$, and then check the following conditions:

  • the $v_1,v_2,\dots,v_6$ are all distinct
  • $(v_2,v_3) \in E$ and $(v_4,v_5) \in E$ and $(v_6,v_1) \in E$.

If all the conditions hold, you've found a cycle; output it

This algorithm has $\Theta(|E|^3)$ running time. Again, it's easy to see that there exist graphs where there are $\Theta(|E|^3)$ cycles and thus any algorithm will need to take at least $\Theta(|E|^3)$ time.


Both of those algorithms are easy to program. That doesn't mean they are necessarily optimal in running time. One could hope for an output-sensitive algorithm whose running time is a function of the number of 6-cycles as well as of $|V|,|E|$. I suspect there are more complex algorithms that might have better asymptotic running time, for some graphs, when considering all three of those parameters. However, they will be much more complex to program. Therefore, by your stated goal of "easiest-to-program", I recommend one of the two algorithms listed above.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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