Testing acyclicity of bounded-degree directed graphs

Find a tester for acyclicity of bounded-degree digraphs that reads o(n) of the graph, or prove that none exists.

shoal State the problem, from Sublinear.info c9f147b · 2周前历史

39 行 · 4.8 KB 原始文件永久链接历史

1	# Testing acyclicity of bounded-degree directed graphs
2
3	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}$.
4
5	## Problem
6
7	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.
8
9	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.
10
11	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?
12
13	## Background
14
15	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](https://tcsopenproblems.com/problem/11) in 2026.
16
17	## What is known
18
19	- 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.
20	- 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.
21	- 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].
22
23	## What would count as progress
24
25	- A tester with $o(n)$ queries for some fixed $d$ and $\varepsilon$, with a proof, even for a natural subclass of bounded-degree digraphs.
26	- 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.
27	- 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.
28
29	## References
30
31	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](https://doi.org/10.1002/rsa.10023)
32	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](https://doi.org/10.1007/s00453-001-0078-7)
33	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](https://arxiv.org/abs/1907.12106)
34	4. Y. Yoshida, Lower bounds for testing directed acyclicity in the unidirectional bounded-degree model, preprint (2026). [arXiv:2604.13577](https://arxiv.org/abs/2604.13577)
35	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](https://doi.org/10.1145/2897518.2897575)
36
37	## Source
38
39	Imported from [Sublinear.info, Problem 41](https://sublinear.info/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.