Testing acyclicity of bounded-degree directed graphs

Can one tell whether a sparse directed graph has no directed cycle, or is far from having none, by looking at a vanishing fraction of it? For dense graphs a number of queries independent of the graph's size suffices, but for bounded-degree graphs no tester is known that beats reading almost the whole graph, and the best lower bound is only $n^{1/3}$.

Problem

Let $G=(V,E)$ be a directed graph on $n$ vertices in which every vertex has in-degree and out-degree at most $d$, a constant. A tester accesses $G$ through its incidence lists, in the bidirectional model: a query $(v, i)$ returns the $i$-th outgoing neighbor of $v$, or the $i$-th incoming neighbor, or reports that there is none. The graph is $\varepsilon$-far from acyclic if at least $\varepsilon d n$ arcs must be deleted to remove every directed cycle.

A tester for acyclicity must accept every acyclic $G$ with probability at least $2/3$ and reject every $G$ that is $\varepsilon$-far from acyclic with probability at least $2/3$; a one-sided tester accepts acyclic graphs with probability 1.

Question. What is the query complexity of testing acyclicity in this model, as a function of $n$ for fixed $d$ and $\varepsilon$? In particular, is there a tester that makes $o(n)$ queries, or are $\Omega(n)$ queries necessary?

Background

Bender and Ron initiated the study of property testing for directed graphs, with acyclicity as the most basic property [1]. In the adjacency-matrix model for dense graphs they gave a tester with $\tilde O(1/\varepsilon^2)$ queries; for sparse graphs, in the bounded-degree model of Goldreich and Ron [2], they proved a polynomial lower bound. Acyclicity is easy to state but its violation is global: a cycle may close only after a long walk, which is what makes local exploration weak. Dana Ron posed the question at the 2011 Bertinoro Workshop on Sublinear Algorithms, and it was posted again on TCS Open Problems in 2026.

What is known

• Bidirectional model. Any two-sided tester needs $\Omega(n^{1/3})$ queries (Bender and Ron, 2002) [1]. For one-sided testers, which can only reject after finding a cycle, the best lower bound is $\Omega(\sqrt n)$. No tester with $o(n)$ queries is known.
• Unidirectional model, where only outgoing arcs can be queried and in-degrees are unbounded. Chen, Randolph, Servedio and Sun proved an $\tilde\Omega(n^{5/9})$ lower bound for one-sided testers (SODA 2020) [3]. Yoshida (2026) improved this to $\tilde\Omega(n^{2/3})$, proved $\Omega(\sqrt n)$ for two-sided testers, and $\Omega(n)$ for tolerant testing [4]. These bounds do not carry over, since a bidirectional tester can also walk backwards along arcs.
• The two models. Czumaj, Peng and Sohler showed that any property testable with a constant number of queries in the bidirectional model is testable with $n^{1-\Omega(1)}$ queries in the unidirectional model [5].

What would count as progress

• A tester with $o(n)$ queries for some fixed $d$ and $\varepsilon$, with a proof, even for a natural subclass of bounded-degree digraphs.
• A lower bound in the bidirectional model above $n^{1/3}$ for two-sided testers or above $\sqrt n$ for one-sided testers, or a linear lower bound settling the question negatively.
• Intermediate steps with the same flavor: tight bounds for non-adaptive testers, or for one-sided testers, in the bidirectional model. A one-sided tester's evidence is a directed cycle, so candidate algorithms are easy to try on random far-from-acyclic graphs before a proof is attempted.

References

1. M. A. Bender and D. Ron, Testing properties of directed graphs: acyclicity and connectivity, Random Structures Algorithms 20(2) (2002), 184–205. doi:10.1002/rsa.10023
2. O. Goldreich and D. Ron, Property testing in bounded degree graphs, Algorithmica 32(2) (2002), 302–343. doi:10.1007/s00453-001-0078-7
3. X. Chen, T. Randolph, R. A. Servedio and T. Sun, A lower bound on cycle-finding in sparse digraphs, SODA 2020; ACM Trans. Algorithms 18(4) (2022). arXiv:1907.12106
4. Y. Yoshida, Lower bounds for testing directed acyclicity in the unidirectional bounded-degree model, preprint (2026). arXiv:2604.13577
5. A. Czumaj, P. Peng and C. Sohler, Relating two property testing models for bounded degree directed graphs, STOC 2016, 1033–1045. doi:10.1145/2897518.2897575

Source

Imported from Sublinear.info, Problem 41, curated by Sublinear.info editors. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.