Difference between revisions of "Open Problems:41"
(Created page with "{{Header |title=Testing Acyclicity |source=bertinoro11 |who=Dana Ron }} Consider the problem of testing acyclicity in ''directed'' bounded-degree graphs (in the incidence list...") |
m (updated header) |
||
| Line 1: | Line 1: | ||
{{Header | {{Header | ||
| − | |||
|source=bertinoro11 | |source=bertinoro11 | ||
|who=Dana Ron | |who=Dana Ron | ||
Latest revision as of 01:54, 7 March 2013
| 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})$.
