Efficient exact search methods improve finding Moore graph structures
Less is Moore
Discrete Mathematics
Summary
Moore graphs are special networks where every point is well connected and close together, but they are very rare and hard to find, especially for certain sizes. The authors focus on how to quickly search for these structures using smarter algorithms, rather than proving if they exist. They improve the search by adding steps that instantly reject bad guesses and by using clever computer tricks that speed up the process on multiple processors. This helps explore the problem more efficiently while using less memory than before.
What this means in practice
- •For graph algorithm developers: Run faster and memory-efficient exact searches for complex graph structures using advanced pruning and parallelization techniques.
- •For network designers: Leverage improved algorithms to explore optimal network topologies with tight connectivity and low diameter properties.
Authors
Paul Stankovski Wagner
Abstract
A Moore graph simultaneously asks for two things that normally pull in opposite directions: every vertex should have many neighbors, while every pair of vertices should remain close. For diameter two and degree $k$, the Moore bound is $k^2+1$, and equality forces a remarkably rigid graph: it is strongly regular with parameters $(k^2+1,k,0,1)$. Hoffman and Singleton showed that such a graph can exist only for $k=2,3,7$, and possibly 57. The degree-57 case on 3,250 vertices remains open. This paper is not an attempt to settle that open problem. Instead, we ask a more algorithmic question: How efficiently can the defining Moore structure itself be searched exactly? We begin from a human-developed exhaustive search based on the radius-two Moore tree. Leaves fall into $k$ groups of size $k-1$, and the edges between every pair of such groups form a perfect matching - a permutation. For efficiency, a partial construction is abandoned immediately when it creates a triangle or quadrangle. We then describe a sequence of exact algorithm-engineering improvements developed through a human-guided AI process and accepted only after mathematical checking and controlled regression tests. The main steps are reversible short-cycle forbid counters, bit-parallel domains, minimum-remaining-value branching, singleton propagation, matching-based AllDifferent filtering, balanced replayable parallel frontiers, residual-symmetry orbit pruning, and canonical deduplication of frontier states. On the principal $k=9$ benchmark, stronger symmetry cuts wall time from 47.6 to 17.9 seconds on a six-core laptop setup. Further parallelization speedup is reported separately; on a 16-core/32-thread machine, median wall time is reduced to 5.28 seconds. Degrees 10 and 57 are used as stress tests, and a five-minute degree-57 run uses only 161 MiB peak resident memory, showing that state size is modest.