Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I wonder if I can make an algorithm to check if a given graph $G=(V,E)$ is acyclic or not with the complexity of $O(|V|)$. I modified the BFS algorithm to do this, but the complexity seems to be $O(|V|+|E|)$.

share|improve this question

3 Answers 3

up vote 7 down vote accepted

If a graph on $n$ nodes has $n$ or more edges then it has a cycle (since trees are the acyclic graphs with the greatest number of edges and have exactly $n-1$ edges). So if your BFS ever traverses $n$ or more edges you may immediately stop and report that the graph has a cycle. Otherwise BFS terminates in $O(n)$ time as there are $n$ nodes and fewer than $n$ edges. In either case the runtime is $O(n)$.

EDIT: As Gerhard Paseman's comment points out this answer assumes an undirected graph.

share|improve this answer
4  
This is true if the graph is undirected. It is a little more tricky for directed graphs. Gerhard "Ask Me About System Design" Paseman, 2011.04.15 –  Gerhard Paseman Apr 16 '11 at 3:33
    
Also, the data structure must allow determination of $|E|$ in $O(|V|)$ time. Not all data structures have this property -- for example, if the graph is presented as an adjacency matrix. –  David Harris Apr 16 '11 at 16:44
    
@David Harris, True. However, as the original question stated a $O(|V|+|E|)$ time algorithm using BFS, I had assumed an adjacency list representation was intended (as an adjacency matrix would require $O(|V|^2)$ time for a BFS). –  Travis Service Apr 16 '11 at 17:41
    
Thanks, I think this is mostly fit to my question, although David's answer is also true. –  Boris Wang Apr 18 '11 at 14:55

The answer for directed acyclic graphs is no: in any standard adjacency-list based representation you have to look at $\Omega(m)$ of the edges; it is not enough to look at $O(n)$ vertices and edges, even if the vertices are already labeled by indegree and outdegree and the adjacency lists are partitioned into incoming and outgoing edges.

For, suppose that you have a directed acyclic graph in the form of a directed path (with $n-1$ edges), partitioned into four equal length subpaths $a_1\dots a_{n/4}$, $b_1\dots b_{n/4}$, $c_1\dots c_{n/4}$, and $d_1\dots d_{n/4}$. For some number of pairs $(i,j)$, add to this path the additional edges in the three-edge path $a_ib_jc_id_j$. This allows the addition of numbers of additional edges ranging from none to $\Omega(n^2)$, and the graph formed in this way is acyclic. But, if your algorithm fails to examine at least one of the edges in any one of these three-edge paths, it could instead be replaced by a path $a_ic_ib_jd_j$, producing a graph with the same indegrees and outdegrees that is not acyclic and that your algorithm cannot distinguish from the given acyclic graph.

This construction doesn't work directly for adjacency matrix representations but in that representation, too, you need more than a linear number of queries; see the Aanderaa–Karp–Rosenberg conjecture and note that the property of containing a cycle is monotone.

share|improve this answer

Well, I think I this thing works : Take any vertex, and start a depht-first.

* Each time you try a new edge uv going out from your current vertex u, check whether you already met v in your traversal. If you did, you have a cycle, otherwise continue
* When you notive you have explored all you could starting from the outneighbors of a vertex v, remove this vertex v from the graph (or just remember that you don't want to see it ever again in your traversals)

The point is : if you take a vertex u such that there is a directed path from one of its outneighbors n1 to one of its in-neighbors n2, then a depth-first-search starting from n1 WILL discover n2 (which will in turn re-discover u -- you found your circuit).

By the way, this algorithm is not in $O(n)$ but in $O(m)$. I posted it because I really don't know how to be more efficient (let's face it, any implemented version of DFS is -- FAST).... I'd be glad to know a better one though :-)

Nathann

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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