A linear query lower bound for graph-isomorphism testing at maximum degree three
- Primary subject
- Computer Science & Software Systems
- Subject subfields
- Algorithms and Complexity · Combinatorics and Graph Theory
- Paper type
- Research Article
- Manuscript stage
- Preprint
For every sufficiently large even N, we exhibit existentially a known connected simple 3-regular N-vertex target whose randomized two-sided isomorphism testing requires Ω(N) incidence queries at literal proximity 0.01, even with connected cubic inputs promised. This gives a negative answer to Goldreich’s Open Problem 4.1 in its stated distance normalization. We also retain maximum-degree-three fixed targets at every sufficiently large integer order, reaching the minimum maximum-degree threshold since degree two admits size-independent query bounds. We use Dror’s sparse-code and adaptive indistinguishability framework. A no-rung 16n-vertex parity encoding has the arbitrary-bijection estimate dist_H(b, Im A) ≤ (2/3) dist_iso(G_b, G_0). Adaptive coloring of imported target middle vertices, a joint defective-row budget, and median assignment rounding handle arbitrary mixing of graph roles. Bounded equivariant surgeries cover every even order with additive distance loss at most 322. An upper bound 4/429 < 0.01 for the older capped family explains why that completion method alone cannot reach the numerical endpoint.