Outerplanar graph testing made faster with random neighbor queries
Testing Induced-Subgraph Freeness in Outerplanar Graphs under the Random-Neighbor Oracle
Data Structures and Algorithms
Summary
Finding certain small patterns inside large outerplanar graphs can be done efficiently using only random neighbor queries. The authors show that for any fixed pattern, it’s possible to test if a big graph contains it by checking only a number of nodes that depends on the error tolerance, not the graph size. This improves on previous methods that needed queries growing with the size of the graph. The testing allows some errors but cannot always guarantee perfect detection, especially for certain simple patterns.
What this means in practice
- •For network engineers: Check for small forbidden structures in large network topologies efficiently using random neighbor sampling to maintain system properties.
- •For database administrators: Quickly verify complex constraints in graph databases modeled as outerplanar graphs with limited query access.
A theory result. No direct application yet.
Authors
Pan Peng, Kefan Yu
Abstract
We prove that, for every fixed nonempty graph $H$, induced-$H$-freeness is testable with $\varepsilon^{-O_H(1)}$ queries on outerplanar graphs with no maximum-degree bound in the $\textit{random-neighbor model}$, where each query at a vertex returns a uniformly random neighbor. Thus, the query complexity is polynomial in $1/\varepsilon$ and independent of the number $n$ of vertices. Previously, the best bound known for this problem was the $\operatorname{poly}(\log n)$-query guarantee that follows from the general outerplanar-graph tester of Babu, Khoury, and Newman (2016) in the stronger $\textit{adjacency-list model}$, which provides exact degree queries and indexed access to neighbors. Our tester has $\textit{two-sided error}$, which is necessary in general: induced-$P_3$-freeness has no one-sided constant-query tester in the random-neighbor model, even on outerplanar graphs of maximum degree two.