Is it possible to check a graph for acyclicity in $O(|V|)$ time?

Question

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|)$.

Answer 1

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.

Answer 2

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.

Answer 3

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