pith. sign in

arxiv: 2604.04466 · v1 · submitted 2026-04-06 · 💻 cs.DS

A characterization of one-sided error testable graph properties in bounded degeneracy graphs

Oded Lachish , Amit Levi , Ilan Newman , Felix Reidl This is my paper

Pith reviewed 2026-05-10 19:57 UTC · model grok-4.3

classification 💻 cs.DS
keywords graph property testingone-sided errorp-degenerate graphsrandom neighbor oracleforbidden subgraphsconnectivitycharacterization
0
0 comments X

The pith

In p-degenerate graphs, a property is one-sided error testable if and only if its violations cannot be fragmented across disjoint high-degree neighborhoods.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper characterizes all one-sided error testable graph properties in p-degenerate graphs under the random neighbor oracle. It proves that such testability holds precisely when the property's defining forbidden structures cannot have their violations fragmented across separate high-degree neighborhoods. This matters because p-degenerate graphs include many real-world networks with hubs, extending earlier results limited to minor-closed families.

Core claim

We show that testability is fundamentally determined by the connectivity of the forbidden structures: a property is testable if and only if its violations cannot be fragmented across disjoint high-degree neighborhoods. Our results define the exact structural boundary for testability under these constraints, accounting for both the connectivity of individual forbidden subgraphs and the collective behavior of the properties they define.

What carries the argument

The connectivity of forbidden structures, which determines whether violations can be fragmented across disjoint high-degree neighborhoods under the random neighbor oracle.

If this is right

  • Properties defined by connected forbidden subgraphs admit one-sided testers with constant query complexity.
  • Properties allowing disconnected violations hidden in separate high-degree hubs require query complexity dependent on graph size.
  • The characterization extends the known complete description for minor-closed families to the broader setting of p-degenerate graphs.
  • Collective properties defined by multiple forbidden structures remain testable only when their interactions cannot be fragmented across hubs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar structural boundaries may exist for testability in other sparse classes such as bounded expansion graphs.
  • Practical algorithms could focus sampling on individual hub neighborhoods to detect connected violations directly.
  • The result raises the question of whether the same connectivity criterion governs testability under related models like the adjacency list oracle.

Load-bearing premise

The random neighbor oracle model and p-degeneracy together capture all relevant exploration constraints, with connectivity of forbidden subgraphs fully determining whether violations can be fragmented.

What would settle it

A concrete graph property with connected forbidden subgraphs that still requires query complexity growing with graph size, or one with disconnected forbidden subgraphs that admits constant-query one-sided testing, in some family of p-degenerate graphs.

Figures

Figures reproduced from arXiv: 2604.04466 by Amit Levi, Felix Reidl, Ilan Newman, Oded Lachish.

Figure 1
Figure 1. Figure 1: The graph H has a separation set S = {a, b, c}. The graph F has m2 copies of H, one for every (i, j) ∈ [m2 ]. Note that the vertex c is present in each of the above copies. Lemma 3.7. Assume that for a 2-connected H, no independent set is a separating set. Then PH is one-sided error testable for the family of p-degenerate graphs. Proof. Let H be a k vertex graph as in the lemma. Let G = (V, E) be a p-degen… view at source ↗
Figure 2
Figure 2. Figure 2: The graph H1 has an obstacle set S = {a, b}. The graph H is a 4-petal cactus, where petal P1 is connected to petal P2 with a vertex taking the role of a, P2 is connected to P3 with a vertex taking the role of b, P3 is connected to P4 via a. H1 a H c a b b P1 P2 P3 P4 P5 C1 C2 a b c a c b b P1 P2 P3 P4 P5 H0 c [PITH_FULL_IMAGE:figures/full_fig_p017_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The graph H1 has a separation set S = {a, b, c}. The graph H is a 5-petal cactus, where petal P2 is connected to petal P1 with a vertex taking the role of a, to P3 with a vertex taking the role of b, and to P4 with c. Then, P4 is connected to P5 with a vertex with role a. Note that P1, which is a subgraph of the component C1, could also be considered a subgraph of the component C2. Thus, the structure of H… view at source ↗
Figure 4
Figure 4. Figure 4: Simulation of bounded-depth BFS using random oracle. [PITH_FULL_IMAGE:figures/full_fig_p032_4.png] view at source ↗
read the original abstract

We consider graph property testing in $p$-degenerate graphs under the random neighbor oracle model (Czumaj and Sohler, FOCS 2019). In this framework, a tester explores a graph by sampling uniform neighbors of vertices, and a property is testable with one-sided error if its query complexity is independent of the graph size. It is known that one-sided error testable properties for minor-closed families are exactly those that can be defined by forbidden subgraphs of bounded size. However, the much broader class of $p$-degenerate graphs allows for high-degree ``hubs" that can structurally hide forbidden subgraphs from local exploration. In this work, we provide a complete structural characterization of all properties testable with one-sided error in $p$-degenerate graphs. We show that testability is fundamentally determined by the connectivity of the forbidden structures: a property is testable if and only if its violations cannot be fragmented across disjoint high-degree neighborhoods. Our results define the exact structural boundary for testability under these constraints, accounting for both the connectivity of individual forbidden subgraphs and the collective behavior of the properties they define.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The paper claims a complete if-and-only-if structural characterization of one-sided error testable graph properties in p-degenerate graphs under the random-neighbor oracle model. A property is testable precisely when its violations cannot be fragmented across disjoint high-degree neighborhoods; this is determined by the connectivity of the forbidden subgraphs (both individually and in their collective behavior), extending the known bounded-forbidden-subgraph result for minor-closed families while accounting for hubs that can hide structure from local exploration.

Significance. If the characterization holds, it is a significant contribution to property testing: it identifies the exact structural boundary separating testable and non-testable properties in the much larger class of p-degenerate graphs, where high-degree vertices can conceal forbidden subgraphs. The result supplies a clean, oracle-specific criterion that could inform query-complexity bounds and algorithm design for sparse graphs beyond minor-closed families.

minor comments (1)
  1. The abstract states that the characterization accounts for 'collective behavior of the properties they define,' yet the provided text does not exhibit the formal statement or proof handling interactions among multiple forbidden subgraphs; the full manuscript should make this explicit.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading of our manuscript and for their accurate summary of our structural characterization. We are pleased that the referee recognizes the potential significance of identifying the precise boundary for one-sided error testability in p-degenerate graphs under the random-neighbor oracle model.

Circularity Check

0 steps flagged

No significant circularity in the structural characterization

full rationale

The paper derives a complete if-and-only-if characterization of one-sided error testable properties in p-degenerate graphs under the random-neighbor oracle: testability holds exactly when violations cannot be fragmented across disjoint high-degree neighborhoods. This follows from structural analysis of the oracle model, degeneracy constraints, and extension of the known bounded-forbidden-subgraph result for minor-closed families (cited to Czumaj and Sohler). No steps reduce by construction to fitted parameters, self-definitions, or load-bearing self-citations; the connectivity condition is presented as an independent structural boundary derived from the model, not presupposed in the inputs. The derivation remains self-contained against external graph-theoretic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on standard definitions of p-degenerate graphs, forbidden subgraphs, and the random neighbor oracle model; no free parameters, ad-hoc axioms, or new invented entities are introduced in the abstract.

axioms (1)
  • standard math Standard definitions of p-degenerate graphs and forbidden-subgraph properties from graph theory.
    The paper builds directly on established concepts in property testing.

pith-pipeline@v0.9.0 · 5501 in / 1137 out tokens · 74752 ms · 2026-05-10T19:57:07.539934+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages

  1. [1]

    Testing of clustering

    Noga Alon, Seannie Dar, Michal Parnas, and Dana Ron. Testing of clustering. SIAM Journal on Discrete Mathematics , 16(3):393--417, 2003

    work page 2003

  2. [2]

    A combinatorial characterization of the testable graph properties: it's all about regularity

    Noga Alon, Eldar Fischer, Ilan Newman, and Asaf Shapira. A combinatorial characterization of the testable graph properties: it's all about regularity. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC) , pages 251--260, 2006

    work page 2006

  3. [3]

    A sufficient condition for characterizing the one-sided testable properties of families of graphs in the random neighbour oracle model

    Christine Awofeso, Patrick Greaves, Oded Lachish, Amit Levi, and Felix Reidl. A sufficient condition for characterizing the one-sided testable properties of families of graphs in the random neighbour oracle model. arXiv preprint arXiv:2511.19027 , 2025

    work page arXiv 2025

  4. [4]

    Testing C k-Freeness in Bounded Admissibility Graphs

    Christine Awofeso, Patrick Greaves, Oded Lachish, Amit Levi, and Felix Reidl. Testing C k-Freeness in Bounded Admissibility Graphs . In 52nd International Colloquium on Automata, Languages, and Programming (ICALP) , pages 15:1--15:20, 2025

    work page 2025

  5. [5]

    H-freeness testing in graphs of bounded r -admissibility

    Christine Awofeso, Patrick Greaves, Oded Lachish, and Felix Reidl. H-freeness testing in graphs of bounded r -admissibility. In 42nd International Symposium on Theoretical Aspects of Computer Science, (STACS) , volume 327, 2025

    work page 2025

  6. [6]

    Testing triangle-freeness in general graphs

    Noga Alon, Tali Kaufman, Michael Krivelevich, and Dana Ron. Testing triangle-freeness in general graphs. SIAM Journal on Discrete Mathematics , 22(2):786--819, 2008

    work page 2008

  7. [7]

    On testability of first-order properties in bounded-degree graphs and connections to proximity-oblivious testing

    Isolde Adler, Noleen K \" o hler, and Pan Peng. On testability of first-order properties in bounded-degree graphs and connections to proximity-oblivious testing. SIAM J. Comput. , 53(4):825--883, 2024

    work page 2024

  8. [8]

    Every monotone graph property is testable

    Noga Alon and Asaf Shapira. Every monotone graph property is testable. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC) , pages 128--137, 2005

    work page 2005

  9. [9]

    A characterization of the (natural) graph properties testable with one-sided error

    Noga Alon and Asaf Shapira. A characterization of the (natural) graph properties testable with one-sided error. SIAM Journal on Computing , 37(6):1703--1727, 2008

    work page 2008

  10. [10]

    Every property of outerplanar graphs is testable

    Jasine Babu, Areej Khoury, and Ilan Newman. Every property of outerplanar graphs is testable. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM) , pages 21--1, 2016

    work page 2016

  11. [11]

    Every minor-closed property of sparse graphs is testable

    Itai Benjamini, Oded Schramm, and Asaf Shapira. Every minor-closed property of sparse graphs is testable. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC) , pages 393--402, 2008

    work page 2008

  12. [12]

    Testable properties in general graphs and random order streaming

    Artur Czumaj, Hendrik Fichtenberger, Pan Peng, and Christian Sohler. Testable properties in general graphs and random order streaming. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM) , 176:16, 2020

    work page 2020

  13. [13]

    A characterization of graph properties testable for general planar graphs with one-sided error (it's all about forbidden subgraphs)

    Artur Czumaj and Christian Sohler. A characterization of graph properties testable for general planar graphs with one-sided error (it's all about forbidden subgraphs). In 60th IEEE Annual Symposium on Foundations of Computer Science, (FOCS) , pages 1525--1548. IEEE Computer Society, 2019

    work page 2019

  14. [14]

    Testing hereditary properties of nonexpanding bounded-degree graphs

    Artur Czumaj, Asaf Shapira, and Christian Sohler. Testing hereditary properties of nonexpanding bounded-degree graphs. SIAM Journal on Computing , 38(6):2499--2510, 2009

    work page 2009

  15. [15]

    Testing c_k -freeness in bounded-arboricity graphs

    Talya Eden, Reut Levi, and Dana Ron. Testing c_k -freeness in bounded-arboricity graphs. In 51st International Colloquium on Automata, Languages, and Programming, (ICALP) , volume 297, pages 60:1--60:20, 2024

    work page 2024

  16. [16]

    Approximately counting and sampling hamiltonian motifs in sublinear time

    Talya Eden, Reut Levi, Dana Ron, and Ronitt Rubinfeld. Approximately counting and sampling hamiltonian motifs in sublinear time. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC) , pages 1043--1054, 2025

    work page 2025

  17. [17]

    Approximating the arboricity in sublinear time

    Talya Eden, Saleet Mossel, and Dana Ron. Approximating the arboricity in sublinear time. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2404--2425. SIAM, 2022

    work page 2022

  18. [18]

    The arboricity captures the complexity of sampling edges

    Talya Eden, Dana Ron, and Will Rosenbaum. The arboricity captures the complexity of sampling edges. In 46th International Colloquium on Automata, Languages, and Programming (ICALP) , volume 132, page 52, 2019

    work page 2019

  19. [19]

    Almost optimal bounds for sublinear-time sampling of k-cliques in bounded arboricity graphs

    Talya Eden, Dana Ron, and Will Rosenbaum. Almost optimal bounds for sublinear-time sampling of k-cliques in bounded arboricity graphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP) , pages 56--1, 2022

    work page 2022

  20. [20]

    Faster sublinear approximation of the number of k-cliques in low-arboricity graphs

    Talya Eden, Dana Ron, and C Seshadhri. Faster sublinear approximation of the number of k-cliques in low-arboricity graphs. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1467--1478. SIAM, 2020

    work page 2020

  21. [21]

    Every testable (infinite) property of bounded-degree graphs contains an infinite hyperfinite subproperty

    Hendrik Fichtenberger, Pan Peng, and Christian Sohler. Every testable (infinite) property of bounded-degree graphs contains an infinite hyperfinite subproperty. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 714--726. SIAM , 2019

    work page 2019

  22. [22]

    Property testing and its connection to learning and approximation

    Oded Goldreich, Shari Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. Journal of the ACM (JACM) , 45(4):653--750, 1998

    work page 1998

  23. [23]

    Property testing in bounded degree graphs

    Oded Goldreich and Dana Ron. Property testing in bounded degree graphs. Algorithmica , 32(2):302--343, 2002

    work page 2002

  24. [24]

    Testing h-freeness on sparse graphs, the case of bounded expansion

    Samuel Humeau, Mamadou Moustapha Kant \' e , Daniel Mock, Timoth \' e Picavet, and Alexandre Vigny. Testing h-freeness on sparse graphs, the case of bounded expansion. In 43rd International Symposium on Theoretical Aspects of Computer Science, (STACS) , volume 364, pages 55:1--55:18, 2026

    work page 2026

  25. [25]

    Local graph partitions for approximation and testing

    Avinatan Hassidim, Jonathan A Kelner, Huy N Nguyen, and Krzysztof Onak. Local graph partitions for approximation and testing. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages 22--31. IEEE, 2009

    work page 2009

  26. [26]

    On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs

    Hiro Ito, Areej Khoury, and Ilan Newman. On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs. computational complexity , 29(1):1, 2020

    work page 2020

  27. [27]

    Every property is testable on a natural class of scale-free multigraphs

    Hiro Ito. Every property is testable on a natural class of scale-free multigraphs. arXiv preprint arXiv:1504.00766 , 2015

    work page arXiv 2015

  28. [28]

    Tight bounds for testing bipartiteness in general graphs

    Tali Kaufman, Michael Krivelevich, and Dana Ron. Tight bounds for testing bipartiteness in general graphs. SIAM Journal on computing , 33(6):1441--1483, 2004

    work page 2004

  29. [29]

    Testing forest-isomorphism in the adjacency list model

    Mitsuru Kusumoto and Yuichi Yoshida. Testing forest-isomorphism in the adjacency list model. In International Colloquium on Automata, Languages, and Programming , pages 763--774. Springer, 2014

    work page 2014

  30. [30]

    Testing triangle freeness in the general model in graphs with arboricity O( n )

    Reut Levi. Testing triangle freeness in the general model in graphs with arboricity O( n ) . In 48th International Colloquium on Automata, Languages, and Programming, (ICALP) , volume 198, pages 93:1--93:13, 2021

    work page 2021

  31. [31]

    Sparsity: graphs, structures, and algorithms

    Jaroslav Neetil and Patrice Ossona de Mendez. Sparsity: graphs, structures, and algorithms . Springer Publishing Company, Incorporated, 2012

    work page 2012

  32. [32]

    Constant-time approximation algorithms via local improvements

    Huy N Nguyen and Krzysztof Onak. Constant-time approximation algorithms via local improvements. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages 327--336. IEEE, 2008

    work page 2008

  33. [33]

    Every property of hyperfinite graphs is testable

    Ilan Newman and Christian Sohler. Every property of hyperfinite graphs is testable. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC) , pages 675--684, 2011

    work page 2011

  34. [34]

    Testing the diameter of graphs

    Michal Parnas and Dana Ron. Testing the diameter of graphs. Random Structures & Algorithms , 20(2):165--183, 2002

    work page 2002