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.
$\begingroup$
$\endgroup$
0
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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.
-
2$\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$ Commented Mar 9, 2013 at 21:45
$\begingroup$
$\endgroup$
2
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)$.
-
9$\begingroup$ You mean to say "it cannot be solved in polynomial time." That's a very different statement than "it cannot be solved" $\endgroup$ Commented Dec 19, 2016 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$– shinzouCommented May 13, 2017 at 18:09