3
$\begingroup$

I'd like to find an efficient algorithm to answer this question: For each node in a directed graph, find whether it is on a non trivial cycle (length > 2)

It sounds simple at first, but I still don't have an efficient sub-quadratic solution. I have some ideas but I'm pretty sure I'm trying to reinvent the wheel. Is there a well known algorithm for this?

For example, to answer the question: For each node in a directed graph, find whether it is on a cycle (of any length) - I just run strongly connected components, and remove all single element component that does not have a self loop, all remaining components have all their nodes in some sort of a cycle

Definitions

I'm not sure if this has any official meaning, but here is my interpretation to these terms for the context of the question:

Trivial Cycle:

A cycle of length 1 or 2 (e.g. only 1 edge in a self loop, or node A points to node B, and node B points to node A, total of 2 edges)

Non Trivial Cycle:

All cycles longer than 2 edges

Requirement

Given a Directed Graph, for each node, tell if it is on a non-trivial cycle

Examples

A = false //because it has no cycles

A<->A = false //because the only cycle is of length 1 edge (self loop)

A<->B = false //because the only cycle is of length 2 edges

A<->B<->C = false //because all cycles are of length 2 edges

A<->B, A<->C = false //because all cycles are of length 2 edges

A->B->C->A = true  // because e.g. A->B->C->A is length 3 edges

A<->B<->C->A = true // because e.g. A->B->C->A is length 3 edges

A<->B<->C<->A = true // because e.g. A->B->C->A is length 3 edges

What I tried

Brute Force: an (at least I think) $O(|E|\times(|E|+|V|))$ or something close to it, which I (probably incorrectly) file under an "~$O(N^2)$ish" algorithm:

  • for each vertex $v$
    • if it has a self loop, temporarily remove it
    • for each outgoing adjacent vertex $w$ (edge $v \rightarrow w$)
      • if there is a path from $w$ back to $v$ (edge $v \leftarrow w$) then temporarily remove that back edge.
        • do BFS/DFS to find whether there is a path starting from $w$ and ending in $v$, if there is one it must be a non trivial path (as we removed all trivial ones) so do an early exit and return true (otherwise return false in the end)

This actually sort of works (although I couldn't come up with a mathematical proof, at least all unit tests pass)

Sketch for a Linear Algorithm: Here is where I'm a bit stuck, I have a gut feeling this can be done in linear time, but I didn't find an existing algorithm for it (doesn't mean there isn't, perhaps I'm just not looking good enough).

The idea sketch is to run strong connected components, then for each component remove all of the forms of A<->A, A<->B, A<->B<->C, A<->B<->C<->D... which I have a feeling can be done in linear time too. Then for all nodes in all components that still have nodes in them, mark them as "true" for "is on non trivial cycle" But this is where it feels that I'm reinventing the wheel. Also if I can't do the math for the Brute force proof, it will be harder for me to do the proof for this.

Questions

  1. Just for sanity, is my quadratic-esque solution indeed ~$O(N^2)$? (assuming I know that the average out degree is some low constant C (e.g. 2) so any O involving V and E can be written as V, C*V)

  2. Main question - is there a linear solution to his problem? Is there a subquadratic one at all? Is there a known algorithm for this? if not, is my sketch a good starting point? Do you think it can be linear? How do I prove it?

$\endgroup$
  • 1
    $\begingroup$ When you say "cycle", do you mean a simple cycle, i.e., no vertex/edge is allowed to be repeated? If so, it would be helpful to edit the question to state that explicitly. Otherwise A<->B<->C has a cycle (a closed walk) of length 4: A->B->C->B->A. $\endgroup$ – D.W. Jul 12 '15 at 5:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.