PaperlayerView exact revision on arXiv

Source-linked AI summary

Testing Induced-Subgraph Freeness in Outerplanar Graphs under the Random-Neighbor Oracle

Pan Peng, Kefan Yu

arXiv:2609.39656v1cs.DS

TL;DR

Unbounded degrees make bounded-radius inspection impractical, while random-neighbor access does not directly expose nonedges. The paper develops structural tools for testing induced patterns on outerplanar graphs, with a dichotomy extending connected-copy search to arbitrary fixed patterns; one-sided constant-query testing is impossible in general.

  • Problem

    Without a maximum-degree bound, a tester cannot inspect every bounded-radius neighborhood with a constant number of queries.

    Source: §1 · p. 2

  • Method

    The approach combines an outerplanar decomposition with a structural dichotomy for disconnected forbidden graphs, then uses recovered bounded-degree lists to simulate the adjacency-list tester.

    Source: §1.2 · p. 6, §3 · p. 8, §7.1 · p. 35

  • Results

    Theorem 16’s dichotomy lets the connected-copy finder extend to testing arbitrary fixed induced patterns.

    Source: §1.2 · p. 6

  • Takeaways & Limitations

    The decomposition preserves each component’s original induced graph after removing only a small number of edges.

    Source: §3 · p. 8

    Induced-P3-freeness cannot be tested with one-sided error and constant query complexity under random-neighbor access, even for outerplanar graphs of maximum degree two.

    Source: §1.1 · p. 4

Abstract

from arXiv · show

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.

1 Introduction

The paper asks whether induced-subgraph freeness can be tested with query complexity independent of n despite random-neighbor access obscuring nonedges. It gives a polynomial-in-1/ε tester for every fixed forbidden graph and outlines structural tools for extending connected-copy search to disconnected patterns.

1.1 Our Contributions

  • For every fixed nonempty H, induced-H-freeness is testable on outerplanar graphs with query complexity polynomial in 1/ε and independent of n.Theorem 1 gives two-sided testing in the random-neighbor model; the bound improves the poly(log n) adjacency-list guarantee of Babu, Khoury, and Newman.Source: §1.1 · p. 3
  • Induced-P3-freeness has no one-sided constant-query tester in the random-neighbor model, even on outerplanar graphs of maximum degree two.The lower bound reflects that finitely many samples may not certify that the complete neighborhood has been seen, even without high degrees.Source: §1.1 · p. 4

1.2 Proof overview and main ideas

  • The tester first uses an adjacency-list algorithm, then simulates it with random-neighbor samples to recover bounded-degree lists; recovery can fail, yielding two-sided error.A single event guarantees correctness of all recovered lists throughout the adaptive execution.Source: §1.2 · pp. 4, 6
  • The decomposition removes O(εn) edges, leaves at most one original high-degree vertex per component, and preserves each component’s induced subgraph.The restriction to outerplanar inputs matters: the analogous small-edit decomposition need not exist for planar graphs, as illustrated by K2,N; this is an obstruction to the decomposition, not an impossibility result for planar testing.Source: §1.2 · pp. 4–5
  • For connected H, candidates are generated by bounded exploration and sampling around a high-degree root, then checked exactly for both edges and nonedges.After discarding candidates with two high-degree vertices, each candidate pair has a low-degree endpoint whose complete list decides adjacency.Source: §1.2 · p. 5
  • For disconnected H, component candidates must be vertex-disjoint with no edges between them; a colored auxiliary graph selects a compatible candidate for each component.If one component has a small removal witness, its separated region supplies candidates for the remaining components.Source: §1.2 · pp. 5–6
  • Theorem 16 gives a dichotomy for disconnected patterns: repeated component search usually retains farness, or one exceptional component has a separated region for the others.This structural tool extends the connected finder to arbitrary fixed induced patterns.Source: §1.2 · p. 6

2 Preliminaries and access models

This section establishes the graph notation, distance measure, and oracle conventions used by the proofs. It also states the partition-oracle guarantee that provides local access to small connected parts.

2 Preliminaries and access models

  • The forbidden graph is represented by component types and their multiplicities, with isolated vertices counted separately from nontrivial components.Repeated components of the same type remain separate indexed components when selecting candidates.Source: §2 · p. 7
  • A random-neighbor query returns an independent uniformly random neighbor, while adjacency-list access provides exact degrees and indexed neighbors.The threshold-list shorthand returns a full list when degree is at most the threshold and otherwise reports High.Source: §2 · p. 7
  • The input is promised outerplanar, but comparison graphs need not be; ε-farness counts edge additions and deletions on the same vertex set, normalized by n.A constant may depend on fixed H and ε, but not on n; ε^-O_H(1) denotes a polynomial in 1/ε.Source: §2 · p. 8
  • A partition oracle returns the part containing a queried vertex without constructing the full partition, with consistent answers for a fixed random seed.For bounded-degree minor-closed graphs, parts have size poly(d/ξ), and with probability at least 2/3 at most ξd|V(X)| edges cross parts.Source: §2 · p. 8

3 Decomposing the graph into induced components

The decomposition gives outerplanar components with at most one high-degree vertex while preserving each component’s original induced graph. A local procedure answers queries about the decomposed graph consistently without constructing it.

3 Decomposing the graph into induced components

  • The construction partitions the low-degree vertices into small connected pieces, separates attached high-degree vertices, then restores every original edge internal to each resulting component.It uses a bounded-degree partition and multiway cuts to form the components.Source: §3 · pp. 8–9
  • The modified decomposition ensures each component contains at most one vertex of degree greater than d and retains all original edges internal to that component.Thus, each component induces the same graph in G′ and G.Source: §3 · pp. 8–9
  • With probability at least 2/3, the decomposition removes at most εn edges, while every component contains at most one vertex whose original degree exceeds d.The edge bound follows from the partition-oracle cut-bound event.Source: §3 · p. 9

3.1 Local access to the decomposition

  • For a fixed seed, local queries consistently access the same decomposed graph, and each invocation uses O(dNpart) threshold-list queries.The local procedure computes component labels to determine whether an edge is retained.Source: §3.1 · p. 10

4 The connected case: algorithm and analysis

For fixed connected H, the section develops an induced-H-freeness tester and analyzes a connected induced-copy finder using low-degree exploration and high-degree-root branch sampling. It establishes polynomial query and success guarantees, including a two-sided-error tester and, under a residual-farness condition, high-probability detection of multiple vertex-disjoint copies.

4 The connected case: algorithm and analysis

  • For fixed connected H, induced-H-freeness is testable with one-sided error using threshold-list access and (1/ε)^O_H(1) queries.The tester uses exact threshold-list queries and direct random-neighbor samples at high-degree roots.Source: §4 · p. 11

4.1 Parameter setting and the threshold-list query

  • One implicit-graph edge-membership query can be simulated with O(dNpart) threshold-list queries.Source: §4.1 · p. 11

4.2 Structural facts for graphs far from induced-freeness

  • If G′ is α-far from induced-F-free, it contains at least αn/(dr) edge-disjoint induced copies, from which a subfamily of at least half has a ρ-fraction of incident edges at every used vertex.Here β = α/(dr) and ρ = β/12; the outerplanar degree-sum bound controls the pruning loss.Source: §4.2 · pp. 12–13

4.3 The connected induced-copy finder

  • The connected-copy finder combines low-degree exploration with high-degree-root branch sampling and finds an induced F-copy with probability at least 1−δ when G′−S is α-far from induced-F-free.It verifies candidates in the original graph, so returned copies are genuine; for d=(1/ε)^O(1), α≥ε^O_F(1), and δ≥ε^O_F(1), its query bound is polynomial in 1/ε.Source: §4.3 · pp. 14–16
  • The finder succeeds per execution with probability at least p_F(α,d) ≥ α^{O_F(1)}d^{-O_F(1)}, handling low-degree copies by exploration and high-degree copies via compatible sampled branches.Its success bound combines the low-degree and high-degree cases; the latter samples branches from a high-degree root and uses their compatibility.Source: §4.3 · pp. 16–17

4.4 Proof of the connected tester

  • Two independent trials make the connected tester always accept induced-H-free inputs and reject ε-far inputs with probability greater than 2/3.Each trial decomposes the graph and runs the finder; the rejection guarantee follows from the per-trial success probability and independent repetition.Source: §4.4 · p. 17

4.5 Finding several vertex-disjoint copies

  • If every residual graph after removing at most K disjoint induced F-copies remains α-far from induced-F-freeness, the fixed-seed finder locates K+1 disjoint copies with probability at least 1−δ.The guarantee applies after each history of successful searches, using the finder with previously found copies excluded and a union bound across stages.Source: §4.5 · p. 18

5 Structural tools for disconnected forbidden graphs

The section develops a structural dichotomy for inputs far from induced-H-freeness: either no forbidden component has a small removal witness, or a unique component does and has a separated region for finding the others. It also gives an outerplanar transversal bound for selecting component copies without cross-edges and shows that repairing the required regions would yield an induced-H-free graph, contradicting the input's distance from freeness.

5 Structural tools for disconnected forbidden graphs

  • Disconnected forbidden graphs require checking that separately found component copies have no edges between them, while a far input may have too few disjoint copies of one component.The exceptional-component alternative addresses this obstruction, which can occur even for forests.Source: §5 · pp. 18–19

5.1 The main structural lemma

  • A far input either has no component with a small removal witness, or has exactly one exceptional component whose witness has a separated region far from every remaining nontrivial component.When isolated components are present, that region also has size at least λn.Source: §5.1 · p. 21

5.2 Rainbow independent transversals

  • In an outerplanar (p, q)-candidate graph, q ≥ 2p guarantees a rainbow independent transversal when p ≥ 2.In the tester’s application, candidate copies are vertices and edges represent forbidden cross-edges.Source: §5.2 · p. 22

5.3 Proof of the structural lemma

  • K1 has no small removal witness, and at most one nontrivial component type can have one; that type occurs only once in H.Source: §5.3 · p. 22
  • For every witness family of the exceptional component, some separated region is η-far from induced-Hi-freeness for each remaining nontrivial component.If H has isolated components, the region also has at least λn vertices.Source: §5.3 · p. 24
  • The proof resolves overlapping repairs through a shared graph and exceptional vertex set, then constructs an induced-H-free graph, contradicting G’s assumed ε-farness.Outside the exceptional set, the constructed graph agrees with each region’s repair, which excludes the corresponding induced component.Source: §5.3 · pp. 25–26
  • There is a region Bj⋆ whose induced subgraph is η-far from induced-Hi-freeness for every i ∈ I+ \ {p}; when m0 > 0, |Bj⋆| ≥ λn.This is the structural alternative obtained after ruling out the possibility that all relevant regions admit the proposed repairs.Source: §5.3 · p. 26
  • Each rooted witness copy Cj is separated from its region Bj: no edge of G joins a vertex of Cj to a vertex of Bj.This follows because vertices in Bj have no edge to the unique high-degree vertex of Cj, and low-degree vertices of Cj have no edge to Bj.Source: §5.3 · p. 26
  • Either no component has a small removal witness with edit budget αn, or the unique such component is nontrivial and its type occurs only once in H.In the latter case, the proof obtains a rooted copy and separated region satisfying alternative (II).Source: §5.3 · p. 27

6 The disconnected case: algorithm and analysis

This section develops and analyzes a one-sided-error threshold-list tester for induced--H-freeness on outerplanar graphs for each fixed disconnected graph H, with query complexity polynomial in 1/ε. The tester combines component-copy searches with local searches in a separated region when a component search stops early, and rejects ε-far inputs with probability above 2/3.

6 The disconnected case: algorithm and analysis

  • Theorem 20 gives a threshold d = (1/ε)^O_H(1) and a one-sided-error tester for induced-H-freeness in outerplanar graphs with total query complexity (1/ε)^O_H(1).H may include isolated vertices and repeated copies of pairwise non-isomorphic connected nontrivial components.Source: §6 · p. 27

6.1 Setting of parameters

  • The parameter setting reuses the connected-case choices, including d ≥ 400K/ε, and applies Theorem 5 with parameter ε/10.The algorithm uses exact threshold-list queries and direct random-neighbor samples at high-degree roots, with a shared seed for each decomposition.Source: §6.1 · p. 27

6.2 Local tools for the exceptional region

  • After constructing Zℓ with O(Khd) threshold-list queries, the tester decides membership in each separated region with one query and searches low-degree regions for induced copies.The low-degree finder samples a vertex and explores to the fixed component’s depth, using the region-membership test while avoiding previously selected vertices.Source: §6.2 · pp. 28–29

6.3 The disconnected tester

  • The tester first seeks K + 1 disjoint copies of each component; if one search stops, it tries the rooted copies’ separated regions to find the remaining components.When every search succeeds, Theorem 17 supplies mutually nonadjacent component copies; when one stops, the exceptional region supports searches for the remaining nontrivial and isolated components.Source: §6.3 · p. 29

6.4 Correctness analysis

  • On induced-H-free inputs the tester never rejects; on far inputs, the two structural cases yield component candidates whose copies form an induced H.In the full-search case, an outerplanar auxiliary graph and Theorem 17 give a rainbow independent transversal; in the exceptional case, selected copies inside Bj have no cross-edges with the rooted witness copy.Source: §6.4 · p. 31
  • A region exists where every relevant induced-Hi-freeness property is η-far, and the algorithm tries that region and finds the required candidates.When m0 > 0, this region also has size at least λn.Source: §6.4 · p. 32
  • Two independent executions reject an ε-far input with probability at least 779/900 > 2/3, while preserving one-sidedness.Conditioned on Gcut, one execution rejects with probability at least 19/20.Source: §6.4 · p. 32

6.5 Query complexity

  • The tester uses (1/ε)^O_H(1) adjacency-list queries for each fixed H, including when the small-input branch reconstructs the graph.The small-input branch uses O(n^2) primitive adjacency-list queries, bounded by (1/ε)^O_H(1).Source: §6.5 · p. 33

7 From adjacency-list access to the random-neighbor model

The section simulates the adjacency-list tester using random-neighbor samples, recovering bounded-degree neighborhoods consistently so the simulated execution matches the exact one when recovery succeeds. This yields a polynomial-in-1/ε query bound independent of n, with two-sided error.

7.1 Recovering bounded-degree neighborhoods

  • Recovery distinguishes high-degree vertices by observing t + 1 distinct neighbors and reconstructs low-degree neighborhoods through repeated samples.The first answer for each pair (v, t) is reused, keeping adaptive queries consistent.Source: §7.1 · p. 34
  • With probability at least 1 − η, all recovered answers are simultaneously correct across at most B queried pairs (v, t), using at most BM random-neighbor queries.The guarantee applies when each threshold is at most D and each recovery call uses M samples.Source: §7.1 · p. 34
  • When every recovered answer is correct, the simulated and exact runs make the same queries, receive the same answers, and return the same output.Using the same random choices also keeps partition-oracle calls tied to one partition and the structural algorithm's calls tied to one graph.Source: §7.1 · p. 35

7.2 The random-neighbor tester

  • The large-input branch compares the simulation with the amplified structural tester; its output can differ only if some recovered record is incorrect.The analysis bounds the probability of any incorrect record and bounds the total number of queries.Source: §7.2 · pp. 36–37
  • The random-neighbor tester achieves ε^-O_H(1) queries independent of n, with two-sided error.Its simulation replaces threshold-list queries with neighborhood recovery while retaining direct random-neighbor sampling at high-degree roots.Source: §7 · p. 33, §7.2 · p. 37

A The one-sided random-neighbor barrier

The appendix rules out constant-query one-sided random-neighbor testing for induced-P3-freeness, even on outerplanar graphs of maximum degree two. It contrasts disjoint unions of paths and triangles, which the oracle cannot distinguish well enough for one-sided soundness.

A The one-sided random-neighbor barrier

  • Disjoint unions of P3’s are exactly n/3 edits from induced-P3-freeness, while the corresponding triangle unions are induced-P3-free.Both graph families are outerplanar and have maximum degree at most two.Source: A The one-sided random-neighbor barrier · p. 39
  • For any q-query algorithm, each complete record is at most 2^q times as likely on the P3-union as on the triangle-union.The bound follows because each queried vertex has degree one or two in the P3-union and degree two in the triangle-union.Source: A The one-sided random-neighbor barrier · p. 39
  • A one-sided tester rejects the induced-P3-free triangle union with probability zero, forcing zero rejection probability on the 1/4-far P3-union and violating soundness.Source: A The one-sided random-neighbor barrier · p. 39

B Proof of the decomposition lemma

The appendix completes the decomposition proof by bounding the edges removed and verifying the resulting components’ structure. The resulting graph G′ is ε-close to G, with each component retaining its original induced subgraph.

B Proof of the decomposition lemma

  • The edge-count proof bounds high–high edges, partition-crossing edges, and multiway cuts to establish the removal budget.The multiway-cut bound uses the high-degree boundary counts and log(2s + 1).Source: B Proof of the decomposition lemma · pp. 39–40
  • The appendix completes Theorem 5 by deriving a polynomial degree-threshold choice from the edge-count and component-structure bounds.Source: B Proof of the decomposition lemma · pp. 39–40
  • At most εn edges are removed before restoration, so G′ is ε-close to G.Restoration only adds original edges and therefore cannot increase the distance from G.Source: B Proof of the decomposition lemma · p. 40
  • Every component of G′ contains at most one vertex whose original degree exceeds d, and its induced subgraph is unchanged from G.The construction separates high-degree vertices before restoring original edges internal to each component.Source: B Proof of the decomposition lemma · p. 40

C AI Disclosure

The authors disclose using ChatGPT as a research and writing assistant. They specify its contributions and state that they independently reviewed and verified the assisted content.

C AI Disclosure

  • The authors developed the main structural ideas and theoretical arguments in Sections 3 and 5.These included the problem formulation, decomposition framework, treatment of disconnected forbidden graphs, and main combinatorial arguments.Source: C AI Disclosure · p. 40
  • ChatGPT materially assisted with algorithms, proofs, intermediate lemmas, parameter checks, and exposition in Sections 4 and 6.It also assisted with notation, organization, and bibliographic checks.Source: C AI Disclosure · p. 40
  • The authors independently reviewed and verified AI-assisted mathematical and bibliographic content and take responsibility for it.Source: C AI Disclosure · p. 40
Loading 2609.39656v1…