Problem 41: Testing Acyclicity

From Open Problems in Sublinear Algorithms
Revision as of 01:54, 7 March 2013 by Krzysztof Onak (talk | contribs) (updated header)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
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})$.