# Problem 41: Testing Acyclicity

From Open Problems in Sublinear Algorithms

Suggested by | Dana Ron |
---|---|

Source | Bertinoro 2011 |

Short link | https://sublinear.info/41 |

Consider the problem of testing acyclicity in *directed* bounded-degree graphs
(in the incidence list model, where one can query both outgoing and
incoming edges).

**Question:** What is the best algorithm for this problem?

**Background:** There is a lower bound of $\Omega(n^{1/3})$
for adaptive, two-sided error algorithms, where $n$ is the number of vertices [BenderR-02].
No sublinear upper bound is known. (For dense graphs, in the adjacency matrix model, one can test
the property using $\operatorname{poly}(1/\epsilon)$ queries.) The best known lower bound for 1-sided error testing is only $\Omega(\sqrt{n})$.