0
$\begingroup$

I would like to detect all the cycles(non duplicate) in a given graph, I mean if A-B-C-A is a cycle, then A-C-B-A is a duplicate of previous one and need to be considered.I could use DFS and detect a cycle, but what if i want to continue to find other cycles? how would i make any node to be considered for other cycle?

$\endgroup$
  • $\begingroup$ There can be exponentially many cycles in a graph, so you could just try every sequence of distinct vertices (up to cyclic permutations) and check whether it's a cycle. $\endgroup$ – Shaull Feb 2 '16 at 10:19
  • 2
    $\begingroup$ @Shaull That would have bad time complexity in terms of output size. $\endgroup$ – Yuval Filmus Feb 2 '16 at 10:40
  • 1
    $\begingroup$ @YuvalFilmus - for a $k$-clique this would be optimal (although there are of course examples on which it would be terrible). $\endgroup$ – Shaull Feb 2 '16 at 10:52
  • $\begingroup$ See cs.stackexchange.com/q/7216/755 and cs.stackexchange.com/q/18342/755. $\endgroup$ – D.W. Feb 4 '16 at 7:59
0
$\begingroup$

Following is an algorithm better than the brute force search.

Given graph $G$, find the DFS tree $T$ of $G$. We know from the structural property of $T$ that any for edge $(u,v)$ in $G$, we have that either $u$ is an ancestor of $v$ in $T$ or $v$ is an ancestor of $u$ in $T$. Therefore, brute force search for cycles in $G$ only along subsets of the branches in $T$. This is equal to the trivial brute force search if $G$ is a clique but better otherwise.

However, one can hope for better heuristics. For instance, see [1].

[1] Hongbo Liu, Jiaxin Wang: A new way to enumerate cycles in graph. AICT/ICIW 2006: 57.

| cite | improve this answer | |
$\endgroup$

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