patternMinor
Number of cycles in a graph?
Viewed 0 times
numbergraphcycles
Problem
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.
I'm looking for a polynomial algorithm for finding all cycles in a graph and was wondering if it's even possible.
Solution
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.
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.
Context
StackExchange Computer Science Q#10427, answer score: 3
Revisions (0)
No revisions yet.