Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2511.10230 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908650491084800 |
|---|---|
| author | Humeau, Samuel Kanté, Mamadou Moustapha Mock, Daniel Picavet, Timothé Vigny, Alexandre |
| author_facet | Humeau, Samuel Kanté, Mamadou Moustapha Mock, Daniel Picavet, Timothé Vigny, Alexandre |
| contents | In property testing, a tester makes queries to (an oracle for) a graph and, on a graph having or being far from having a property P, it decides with high probability whether the graph satisfies P or not. Often, testers are restricted to a constant number of queries. While the graph properties for which there exists such a tester are somewhat well characterized in the dense graph model, it is not the case for sparse graphs. In this area, Czumaj and Sohler (FOCS'19) proved that H-freeness (i.e. the property of excluding the graph H as a subgraph) can be tested with constant queries on planar graphs as well as on graph classes excluding a minor.
Using results from the sparsity toolkit, we propose a simpler alternative to the proof of Czumaj and Sohler, for a statement generalized to the broader notion of bounded expansion. That is, we prove that for any class C with bounded expansion and any graph H, testing H-freeness can be done with constant query complexity on any graph G in C, where the constant depends on H and C, but is independent of G.
While classes excluding a minor are prime examples of classes with bounded expansion, so are, for example, cubic graphs, graph classes with bounded maximum degree, graphs of bounded book thickness, or random graphs of bounded average degree. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_10230 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Testing H-freeness on sparse graphs, the case of bounded expansion Humeau, Samuel Kanté, Mamadou Moustapha Mock, Daniel Picavet, Timothé Vigny, Alexandre Data Structures and Algorithms Combinatorics In property testing, a tester makes queries to (an oracle for) a graph and, on a graph having or being far from having a property P, it decides with high probability whether the graph satisfies P or not. Often, testers are restricted to a constant number of queries. While the graph properties for which there exists such a tester are somewhat well characterized in the dense graph model, it is not the case for sparse graphs. In this area, Czumaj and Sohler (FOCS'19) proved that H-freeness (i.e. the property of excluding the graph H as a subgraph) can be tested with constant queries on planar graphs as well as on graph classes excluding a minor. Using results from the sparsity toolkit, we propose a simpler alternative to the proof of Czumaj and Sohler, for a statement generalized to the broader notion of bounded expansion. That is, we prove that for any class C with bounded expansion and any graph H, testing H-freeness can be done with constant query complexity on any graph G in C, where the constant depends on H and C, but is independent of G. While classes excluding a minor are prime examples of classes with bounded expansion, so are, for example, cubic graphs, graph classes with bounded maximum degree, graphs of bounded book thickness, or random graphs of bounded average degree. |
| title | Testing H-freeness on sparse graphs, the case of bounded expansion |
| topic | Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2511.10230 |