Graph testers spot forbidden patterns efficiently using arboricity
Tolerant Testers for Subgraph-Freeness
Data Structures and Algorithms
Summary
Finding forbidden patterns like triangles or cliques inside large graphs can be hard, especially when you want to tolerate small errors or noise. The authors designed algorithms that efficiently check if a graph mostly has no such patterns, using a complexity measure called arboricity that describes how dense the graph is. Their testers work well on various shapes and improve earlier methods by reducing dependence on graph size or degree bounds. This means it’s easier to analyze big networks for certain patterns without examining the entire structure.
What this means in practice
- •For network analysts: Detect approximate presence or absence of small forbidden patterns in large networks more efficiently using arboricity-based testers.
- •For database engineers: Check for near-perfect absence of specific small subgraphs in large graph-structured data sets without exhaustive inspection.
Authors
Reut Levi, Jonathan Meiri
Abstract
In this paper we study the problem of tolerantly testing the property of being $H$-free (which also implies distance approximation from being $H$-free). In the general-graphs model, we show that tolerant $K_k$-freeness testing can be achieved with query complexity that is polynomial in the arboricity of the input graph $G$, $arb(G)$, and independent of the size of $G$ (for graphs in which the average degree is $Ω(1))$. Specifically for triangles, our algorithm distinguishes graphs which are $ε$-close to being triangle-free from graphs that are $3ε(1+η)$-far from being triangle-free with expected query complexity which is $\tilde{O}(arb^3(G))$ (for constant $η$ and $ε$). For general $k$-cliques our algorithm distinguishes graphs which are $ε$-close to being $K_k$-free from graphs which are ${k \choose 2}ε(1+η)$-far from being $K_k$-free with expected query complexity which is polynomial in $k$, $1/ε$, $1/η$ and $arb(G)$. We then generalize our result and provide a similar result for any motif $H$ which is $2$-connected and has radius $1$. This includes for example the wheel graph. Finally, we show that our tester can be applied to the bounded-degree model for tolerantly testing $H$-freeness for any motif $H$. The query complexity of the algorithm is polynomial in the degree bound, $d$, improving the previous state-of-the-art by Marko and Ron (TALG 2009) that obtained quasi-polynomial query complexity in $d$.