3
$\begingroup$

Can the number of cycles in a graph (undirected/directed) be exponential in the number of edges/vertices?

I'm looking for a polynomial algorithm for finding all cycles in a graph and was wondering if it's even possible.

$\endgroup$
3
$\begingroup$

Assuming you mean simple cycles (otherwise the number is infinite) - yes, of course the number can be exponential: consider the complete graph on $n$ vertices, then every sequence of distinct vertices can be completed to a simple cycle. So you get at least $n!$ cycles.

Even if you ignore cyclic permutations of a cycle, this is still exponential: you can take only cycles of length $n/2$, and you have more than ${n\choose n/2}$ such cycles.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ there are only $\leq n$ cyclic permutations of any cycle. you could also exclude any the reverse of any cycle, and you still have $\geq 0.5 (n-1)!$ $\endgroup$ – Sasho Nikolov Mar 9 '13 at 21:45
3
$\begingroup$

The problem you want to solve is #CYCLE. Unless P=NP, it cannot be solved, for a proof look at the chapter on Counting Complexity in Arora and Barak. It is a gadget construction that reduces solving Hamiltonian path to #CYCLE and hence unless P=NP, Hamiltonian cycle - a NP-Complete problem cannot have a poly time solution.

As for the first question, as Shauli pointed out, it can have exponential number of cycles. Actually it can have even more - in a complete graph, consider any permutation and its a cycle hence atleast n! cycles. Actually a complete graph has exactly (n+1)! cycles which is $O(n^n)$.

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ You mean to say "it cannot be solved in polynomial time." That's a very different statement than "it cannot be solved" $\endgroup$ – Stella Biderman Dec 19 '16 at 17:11
  • $\begingroup$ The gadget just shows a reduction from HAM to #CYCLE, how does that tell you of a way to count simple cycles? what if the graph has many cycles but not hamilton cycles? $\endgroup$ – shinzou May 13 '17 at 18:09

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.