Lower Bounds for Testing Directed Acyclicity in the Unidirectional Bounded-Degree Model
Yuichi Yoshida · 2026
Read Lower Bounds for Testing Directed Acyclicity in the Unidirectional Bounded-Degree Model by Yuichi Yoshida (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-13577.txt.
Introduction
Yoshida proves new lower bounds for testing whether a directed graph has cycles when each query reveals only a vertex's outgoing neighbors. Any one-sided tester needs roughly n to the two-thirds power queries, improving the prior n to the five-ninths bound. A two-sided tester still needs about the square root of n queries. For tolerant testing, he shows a linear lower bound by reduction from bounded-degree three-colorability.
Catalog record
| CREATOR | Yuichi Yoshida |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 92161 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.13577
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Lower Bounds for Testing Directed Acyclicity in the Unidirectional Bounded-Degree Model Yuichi Yoshida Abstract We study property testing of directed acyclicity in the unidirectional bounded-degree oracle model, where a query to a vertex reveals its outgoing neighbors. We prove that there exist absolute constants d 0 ∈ ℕ d_{0}\in\mathbb{N} and ε > 0 \varepsilon>0 such that for every constant d ≥ d 0 d\geq d_{0} , any one-sided ε \varepsilon -tester for acyclicity on n n -vertex digraphs of maximum outdegree at most d d requires Ω ~ ( n 2 / 3 ) \widetilde{\Omega}(n^{2/3}) queries. This improves the previous Ω ~ ( n 5 / 9 ) \widetilde{\Omega}(n^{5/9}) lower bound for one-sided testing of acyclicity in the same model. We also prove that, under the same degree assumption, any two-sided ε \varepsilon -tester requires Ω ( n ) \Omega(\sqrt{n}) queries, improving the previous Ω ( n 1 / 3 ) \Omega(n^{1/3}) lower bound. We further prove an Ω ( n ) \Omega(n) lower bound for tolerant testing for some absolute constant outdegree bound d d by reduction from bounded-degree 3 3 -colorability. 1 Introduction Property testing studies whether one can distinguish objects that satisfy a property from objects that are far from satisfying it by making only a small number of local queries [ 3 , 9 , 7 ] . For sparse graphs, Goldreich and Ron [ 8 ] introduced the bounded-degree oracle model, where a query specifies a vertex and an index and returns the corresponding neighbor, thereby restricting the tester to local access. For directed graphs, testing acyclicity is one of the most basic problems: the property is monotone and easy to state, but its violation is inherently global, since a directed cycle may close only after many locally innocuous steps. This tension becomes especially pronounced in the unidirectional bounded-degree model, where a query reveals only the outgoing neighbors of a vertex, so a local exploration may continue to see only tree-like outward neighborhoods for a long time even when the underlying graph is far from acyclic. A simple general upper bound is the trivial O(n) -query exploration of the whole graph, so lower bounds play a central role in understanding the problem. In this paper, we prove new lower bounds for the following problem in the unidirectional bounded-degree oracle model. The input is a directed graph G=(V,E) on n vertices with maximum outdegree at most d=O(1) but no bound on indegree, and a query to a vertex reveals the ordered list of its outneighbors. For a proximity parameter \varepsilon>0 , testing acyclicity means distinguishing acyclic graphs from graphs that are \varepsilon -far from acyclic, where distance is measured by edge deletions: we say that G is \varepsilon -far from acyclic if at least \varepsilon dn edges must be removed to destroy all directed cycles. We consider the three standard testing settings: one-sided, two-sided, and tolerant. In one-sided testing, the tester must accept every acyclic graph with probability 1 ; for acyclicity, this means that it can reject only after the revealed subgraph already contains a directed cycle. In two-sided testing, the tester may err with small probability on both acyclic and \varepsilon -far inputs. In tolerant testing, the goal is instead to distinguish graphs that are close to acyclic from graphs that are far from acyclic. We show the following lower bounds for testing acyclicity in the one-sided, two-sided, and tolerant settings. Here \widetilde{\Omega} suppresses polylogarithmic factors. • For every sufficiently large constant outdegree bound d , one-sided testing requires \widetilde{\Omega}(n^{2/3}) queries (Theorem 4.10 ). • For every sufficiently large constant outdegree bound d , two-sided testing requires \Omega(\sqrt{n}) queries (Theorem 5.6 ). • For some absolute constant outdegree bound d , tolerant testing requires \Omega(n) queries (Theorem 6.8 ). For quick reference, Table 1 compares our three lower bounds with the prior lower bounds most directly related to ours. Setting Previous bound This work One-sided \widetilde{\Omega}(n^{5/9}) [ 5 ] \widetilde{\Omega}(n^{2/3}) Two-sided \Omega(n^{1/3}) [ 1 ] \Omega(\sqrt{n}) Tolerant — \Omega(n) Table 1: Comparison between the lower bounds proved here and representative prior lower bounds most directly related to ours. Note that the two-sided lower bound of Bender and Ron [ 1 ] is proved in the model where both indegree and outdegree are bounded. 1.1 Technical Overview The hard instance. The one-sided lower bound is based on a construction that separates the source of cyclicity from the part of the graph that dominates much of the exploration. The hidden graph is partitioned into two regions: a blue core of linear size, where all directed cycles live, and a red region, which is acyclic and split into \Theta(n^{1/3}) forward-only layers of size \Theta(n^{2/3}) . Inside the blue core, each blue vertex points to the images of a constant number of independent random permutations of the blue set, so the induced blue subgraph behaves like a random constant-outdegree digraph and is linearly far from acyclic. Inside the red region, edges go only forward, and each blue vertex also sends a constant number of edges into the first half of the red layers. Consequently, even when the algorithm starts from a blue vertex, a constant fraction of the revealed edges leaves the blue core and enters an acyclic region. Since red vertices never point back into blue, every directed cycle is contained in the hidden blue core, while the red region disperses the exploration. The construction remains close in spirit to the construction of Chen, Randolph, Servedio, and Sun [ 5 ] , in which a hidden blue region contains all cycles and a red layered region absorbs exploration. The differences relevant to our proof are the following. First, the blue-to-blue edges are not sampled together with the blue-to-red edges from one common pool. Instead, each blue vertex has d_{B} blue edges coming from independent random permutations of B , and its d_{R} red edges are sampled separately from R_{\leq L/2} . This permutation structure later lets us condition on the entire transcript and still regard a fresh blue edge as a uniformly random unused blue image. Second, a red vertex does not deterministically move from layer R_{i} to the next layer R_{i+1} as in [ 5 ] ; each red edge jumps to a uniformly random later layer in a window of length L/2 . The red subgraph remains acyclic, but the red region no longer carries a rigid notion of depth. These changes address the weaknesses of the CRSS instance identified in [ 5 ] . When every red edge goes to the next layer, the red region can serve as a coordinate system: simple sink-distance information can reveal layer information, and wall-building procedures that systematically expose the red zone can help guide the search back toward blue vertices [ 5 , Section 8] . Our forward-jumping red edges remove that geometry. The permutation-based blue core also provides a deferred-decisions view, meaning that after conditioning on the transcript a fresh blue edge is still uniform over the remaining unused blue images, strong enough for the closure analysis in the one-sided proof. Moreover, the lower bound is proved in a model that is stronger for the tester: in the later decomposition of