Instant TravelLuminary Oddities — Enter the Portal
Research Archive

Research Article · Preprint Computer Science & Software Systems

A linear query lower bound for graph-isomorphism testing at maximum degree three

Scott Schubr

Luminary Oddities LLC

  • Computer Science & Software Systems
  • Algorithms and Complexity
  • Combinatorics and Graph Theory
Primary subject
Computer Science & Software Systems
Subject subfields
Algorithms and Complexity · Combinatorics and Graph Theory
Paper type
Research Article
Manuscript stage
Preprint
Manuscript
Archived
Edition
2 · Permanent link

You are reading a preserved edition. Read the current edition (v3).

Read / download PDF Publication filesCite this edition

Overview

Abstract

For every sufficiently large N, this paper exhibits existentially a known simple N-vertex graph of maximum degree at most three for which randomized two-sided isomorphism testing in the incidence-query model requires Ω(N) queries at an absolute positive proximity parameter. This sharpens Dror’s maximum-degree-thirteen construction and reaches the minimum maximum-degree threshold, since degree two admits size-independent query bounds. The proof retains Dror’s sparse binary-code and adaptive indistinguishability framework and supplies a constant-size subcubic encoding with a one-bit incidence oracle. An arbitrary-bijection distance bound follows from local recognition of variable and parity components and partial decoding outside edge defects. For every sufficiently large even order, the paper further obtains connected simple 3-regular targets, with the same promise on the input graphs, at proximity 10⁻⁹. This strengthening uses intrinsically recognizable cubic caps, robust core recovery and symmetry-preserving padding.

Keywords graph isomorphism testing · bounded-degree graphs · incidence queries · connected cubic graphs · subcubic graphs · query complexity · robust decoding

Scope of the work

The results concern classical randomized two-sided incidence-query testing against existential known targets, with unrestricted target preprocessing and computation. The all-order maximum-degree-three theorem retains proximity 10⁻⁶; the connected simple 3-regular theorem covers sufficiently large even orders at proximity 10⁻⁹, even with connected cubic inputs promised. Efficient uniform construction, quantum lower bounds and computational graph-isomorphism hardness are not asserted. The literal proximity-0.01 question remains unresolved. The paper credits its sparse-code, CFI, robust-decoding and cubic-completion ingredients.

Reproduction notes

The fifteen-member package contains the complete nine-page manuscript, self-contained LaTeX source and bibliography, five standard-library Python verification programs, five public result files, reader instructions, citation metadata and a checksum manifest. With Python 3.10 or later, run verify_encoding.py, verify_combinatorics.py, verify_cubic.py, verify_core_transfer.py and verify_connectivity.py with distinct --output filenames, then repeat under python -O. Keep the files together and follow README.md for comparison rules; the combinatorial optimized receipt differs only in its optimized Boolean. Build main.tex with Tectonic or two pdflatex runs. Finite checks corroborate the encoding, exact combinatorics, cubic components, core transfer and connectivity estimates; the asymptotic lower bounds follow from the analytic proofs.

The manuscript

Read the paper

Open PDF

The complete manuscript, as published in this edition.

If the reader is unavailable on your device, open or download the PDF directly.

Author disclosures

AI-assisted tools supported research exploration, literature review, manuscript preparation and internal verification. The author retains responsibility for the work. Internal AI-assisted and computational checks are distinct from external human peer review.

References and related publications

  1. A. Dror, A Linear Lower Bound on Testing Graph Isomorphism in the Bounded-Degree Model, ECCC TR26-268 (2026).
  2. O. Goldreich and L. Tauber, Testing in the Bounded-Degree Graph Model with Degree Bound Two, LNCS 15700 (2025), 373–382.
  3. O. Goldreich, Testing Isomorphism in the Bounded-Degree Graph Model, LNCS 15700 (2025), 293–323.
  4. O. Goldreich and L. Tauber, On Testing Isomorphism to a Fixed Graph in the Bounded-Degree Graph Model, LNCS 15700 (2025), 324–337.
  5. J.-Y. Cai, M. Fürer and N. Immerman, An optimal lower bound on the number of variables for graph identification, Combinatorica 12 (1992), 389–410.
  6. V. Arvind, J. Köbler, S. Kuhnert and Y. Vasudev, Approximate Graph Isomorphism, MFCS 2012, LNCS 7464, 100–111.
  7. R. O’Donnell, J. Wright, C. Wu and Y. Zhou, Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs, SODA 2014, 1659–1677.
  8. Y. Chen, J. Flum and M. Liu, Some remarks on the uncolored versions of the original CFI-graphs, arXiv:2507.01459 (2025).
  9. M. Goetze, P. Jungeblut and T. Ueckerdt, Recognition Complexity of Subgraphs of k-Connected Planar Cubic Graphs, Algorithmica 88 (2026), article 11.

A stable scholarly record

Cite this edition

Scott Schubr. (2026). A linear query lower bound for graph-isomorphism testing at maximum degree three (Version 2). Luminary Research Archive. https://research.luminaryoddities.com/linear-query-lower-bound-graph-isomorphism-testing-maximum-degree-three/v/2

BibTeX
@techreport{luminary_linear_query_lower_bound_graph_isomorphism_testing_maximum_degree_three_v2,
  title = {A linear query lower bound for graph-isomorphism testing at maximum degree three},
  author = {Scott Schubr},
  year = {2026},
  institution = {Luminary Research Archive},
  type = {Research Article},
  note = {Version 2},
  url = {https://research.luminaryoddities.com/linear-query-lower-bound-graph-isomorphism-testing-maximum-degree-three/v/2}
}

Loading discussion…