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

Samuel Humeau, Mamadou Moustapha Kanté, Daniel Mock, Timothé Picavet, Alexandre Vigny · 2025

Read Testing H H -freeness on sparse graphs, the case of bounded expansion by Samuel Humeau, Mamadou Moustapha Kanté, Daniel Mock, Timothé Picavet, Alexandre Vigny (2025) 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-2511-10230.txt.

Introduction

Samuel Humeau, Mamadou Moustapha Kanté, Daniel Mock, Timothé Picavet, and Alexandre Vigny prove that testing whether a sparse graph contains a forbidden subgraph takes only constantly many queries. In property testing, an algorithm samples a graph and must accept graphs with the property and reject graphs far from it. For dense graphs the testable properties are fairly understood, but sparse graphs lagged behind.

Earlier work by Czumaj and Sohler settled the question for planar and minor-free graphs. Using the sparsity toolkit, this team gives a simpler proof for the broader setting of bounded expansion classes, which include bounded-degree and bounded book-thickness graphs. The query count depends on the forbidden graph and the class, but never on the size of the graph being tested.

Catalog record

CREATORSamuel Humeau, Mamadou Moustapha Kanté, Daniel Mock, Timothé Picavet, Alexandre Vigny
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE61 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-10230

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Testing H H -freeness on sparse graphs, the case of bounded expansion Samuel Humeau, Mamadou Moustapha Kanté, Daniel Mock, Timothé Picavet, Alexandre Vigny Abstract 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 P , it decides with high probability whether the graph satisfies P 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 H -freeness (i.e. the property of excluding the graph H 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 𝒞 {\mathcal{C}} with bounded expansion and any graph H H , testing H H -freeness can be done with constant query complexity on any graph G G in 𝒞 {\mathcal{C}} , where the constant depends on H H and 𝒞 {\mathcal{C}} , but is independent of G 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. ENS de Lyon, CNRS, LIP, UMR 5668, 69342, Lyon cedex 07, [email protected]://orcid.org/0009-0007-1850-9744 Université Clermont Auvergne, Clermont Auvergne INP, LIMOS, CNRS, Clermont-Ferrand, [email protected]://orcid.org/0000-0003-1838-7744 RWTH Aachen University, [email protected]://orcid.org/0000-0002-0011-6754Supported by the Deutsche Forschungsgemeinschaft (DFG, German Science Foundation) – DFG-927/15-2 LaBRI, Université de Bordeaux, [email protected]://orcid.org/0000-0002-7129-0127 University Clermont Auvergne, [email protected]://orcid.org/0000-0002-4298-8876 {CCSXML} ¡ccs2012¿ ¡concept¿ ¡concept_id¿10002950.10003624.10003633.10010917¡/concept_id¿ ¡concept_desc¿Mathematics of computing Graph algorithms¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡concept¿ ¡concept_id¿10003752.10003809.10010055¡/concept_id¿ ¡concept_desc¿Theory of computation Streaming, sublinear and near linear time algorithms¡/concept_desc¿ ¡concept_significance¿300¡/concept_significance¿ ¡/concept¿ ¡/ccs2012¿ ccs Mathematics of computing Graph algorithms ccs Theory of computation Streaming, sublinear and near linear time algorithms keywords Property testing, Sparsity, Bounded expansion, Treedepth † † runningauthor: S. Humeau, M.M. Kanté, D. Mock, T. Picavet, and A. Vigny † † copyright: Samuel Humeau, Mamadou Moustapha Kanté, Daniel Mock, Timothé Picavet, and Alexandre Vigny † † editors: John Doe † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction Given some data with a question, do you need to read all the data to answer, or can you parse only a fraction of it before answering correctly with high probability? The domain of study associated to such problems is known as property testing . Intuitively, a property testing algorithm (or tester ) takes a graph G and a property P as inputs, accepts with high probability if G satisfies P , and rejects with high probability if G is “ far ” from having property P . The notion of being “far” from having a property is often described via the fraction \epsilon of edge additions or edge removals needed to transform G into a graph G^{\prime} satisfying P . The fixed fraction \epsilon is often called the proximity parameter . A tester accepting with probability one on graphs satisfying P has one-sided error . Otherwise, the tester has two-sided error . A tester does not have direct access to its input graph. Instead it uses an oracle , i.e. a “black box” serving as a representation of the input graph to which queries can be made. These depend on context and can be, for example: “are these two vertices neighbors?” or “give me a random neighbor of this vertex”. There exists several models formalizing the notions described above: the dense, sparse, and bounded degree models, and they differ on how “being far from a property” is defined and on the available queries. The efficiency of testers is quantified by the number of queries, called query complexity , made to a given representation of G . Ideally, the number of queries is constant: it depends on the property P and the proximity parameter \epsilon of “being far from P ”, but not on G . In this case, P is called testable with constant query complexity , or testable . More formally, in the dense graph model introduced by Goldreich, Goldwasser, and Ron [ 10 ] , a graph G is said to be \epsilon -close to a property P if changing at most a fraction \epsilon of its adjacency matrix (i.e. at most \epsilon\cdot|V(G)|^{2} many edges) transforms G into a graph G^{\prime} satisfying P . Otherwise G is called \epsilon -far from P . For this model, there is a good understanding of what properties are testable with two-sided error [ 2 ] , but also one-sided [ 3 , 4 ] . For example, every hereditary property (i.e. stable under taking induced subgraphs; such as bipartite, H -free or k -colorable) are one-sided error testable in the dense model. In the bounded degree model [ 11 ] , the input comes with an integer d and every vertex of the input is assumed to have degree at most d . In this case, it is known that restricting the class further to planar graphs, or graphs that exclude a minor (i.e. proper minor closed classes of graphs), and, more generally, to hyperfinite graph classes, allows every property to be testable with two-sided error [ 15 ] . For the more general case where only the degree constraint is considered, far fewer properties can be tested efficiently. On the one hand, it is known that testing FO-properties of the form \exists\forall can be done efficiently. This includes testing for H -freeness. On the other hand some \forall\exists -FO formulas cannot be tested efficiently [ 1 ] . One of the most important property that cannot be tested is bipartiteness, which requires (on general graphs with bounded degree) \Omega(\sqrt{|G|}) many queries. See chapter nine of [ 12 ] . The sparse model is currently the less known model. It splits into slightly different variations, depending on whether from a given vertex the algorithm can query: 1) it’s i th neighbor (upon input an integer i , and receives an error if the vertex has less than i neighbors), or 2) a random neighbor (possibly several times the same), or 3) a random distinct neighbor (distinct from the outputs of previous queries on the same vertex). We refer to the introduction of [ 8 ] for more information and, similarly to the recent work in this area [ 5 , 6 , 7 , 9 ] . We focus here on the random neighbor model , i.e., the second variation of the sparse model as presented above. Observe that a query in this variation can be simulated using a constant number of queries in the other variations. Hence any property testable in the random neighbor model

Read the complete text