Luminary Research Archive
Luminary Research ArchiveIndependent scholarship
Luminary Portal
PublicEdition 5

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

Scott Schubr

Original PDF · First-page preview

Loading original first page…

Abstract

We give a negative answer to Goldreich's Open Problem 4.1: fixed-target isomorphism testing for cubic graphs need not admit sublinear query complexity at proximity 0.01. For every sufficiently large even N, there exists a known connected simple 3-regular N-vertex target requiring Ω(N) randomized two-sided incidence queries, even when inputs are promised connected and cubic. The normalization is the stated unordered-edge threshold 0.01(3N/2), and computation and target preprocessing are unrestricted. Within Dror's sparse-code framework, a 16n-vertex encoding satisfies dist_H(b,im A)≤(2/3)dist_iso(G_b,G_0) under arbitrary uncolored bijections, including equal isolate padding. Adaptive target-middle colors, a joint row-defect budget and median rounding establish this estimate. Bounded equivariant surgeries cover every even order. The same encoding gives proximity-0.01 hardness at every sufficiently large integer order by adding at most 47 isolates; an alternative using the surgeries needs at most one isolate. Thus one construction also reaches the minimum possible maximum-degree threshold, namely three.

Read the full paper in the original PDF.

Edition files

  • paper.pdf114.7 KiB · pdf
    SHA-2565ebf19b5b5a20744ede0a1ba8d630fa9f08ecb4f83e5c628e9fe59990da12bc7
  • Graph_Testing_Publication.zip172.9 KiB · package
    SHA-2566e396e32c9f42bd5fe59eb900fe9a5849847cbfede973d38c9021092ccc34e28

Available editions

  1. Edition 7 · 2026-11-02 · public
  2. Edition 6 · 2026-10-27 · public
  3. Edition 5 · 2026-10-27 · public
  4. Edition 4 · 2026-10-24 · public
  5. Edition 3 · 2026-10-24 · public
  6. Edition 2 · 2026-10-24 · public
  7. Edition 1 · 2026-10-24 · public

Research details

Subjects
Mathematics · Computer Science & Software Systems · Combinatorics and Graph Theory · Algorithms and Complexity
Keywords
graph isomorphism testing, bounded-degree graphs, incidence queries, connected cubic graphs, subcubic graphs, query complexity, robust decoding
Manuscript date
2026-10-23
Reader reuse
No additional permission granted

Scope

For every sufficiently large even order, an existential known connected simple cubic target requires linear randomized two-sided incidence queries at proximity 0.01, including connected cubic inputs; one encoding also covers all large orders with bounded isolate padding.

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.

Reproduction

The 11-page manuscript and complete editable LaTeX sources are supplied in this 21-member package. README.md gives the build and reproduction commands. Reproducibility code: verify_all_orders.py, verify_combinatorics.py, verify_connectivity.py, verify_core_transfer.py, verify_cubic.py, verify_encoding.py, verify_literal.py, verify_proximity.py. The accompanying manuscript and reader instructions specify the mathematical scope and required dependencies.

References and related resources

  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; Open Problem 4.1.
  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.
  10. I. Adler, N. Köhler and P. Peng, On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing, SIAM J. Comput. 53(4) (2024), 825–883.
  11. K. Makarychev, R. Manokaran and M. Sviridenko, Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-based Approximation Algorithm, arXiv:1403.7721 (2014).