A new record of enumeration of regular graphs by parallel processing

Zhipeng Xu, Xiaolong Huang, Fabián Jiménez, Yuefan Deng

Abstract

This study reports a new milestone in graph theory: the enumeration of non-isomorphic 4-regular graphs of order 23. By adapting the classical GENREG algorithm for massive parallel execution on international supercomputers, we expanded the OEIS sequence A006820, identifying exactly 429,668,180,677,439 graphs. Beyond the counting record, our search identified several optimal regular graphs with minimum diameters, offering potential improvements for interconnection network topologies in high-performance computing.

Introduction

In graph theory, enumeration involves listing all possible graphs meeting specific criteria—such as being "regular" (where every vertex has the same degree $k$)—without redundant counting of isomorphic structures. While seemingly abstract, regular graphs are foundational to computer architecture. The interconnection networks of supercomputers are essentially large regular graphs; finding topologies with the smallest Average Shortest Path Length (ASPL) is critical for reducing communication latency.

However, the "combinatorial explosion" makes this task exponentially difficult as the number of vertices (order $n$) grows. The previous record for 4-regular graphs (quartics) had remained at $n=22$ since 2011. This work breaks that eight-year-old barrier.

Methodology: Scaling GENREG for Supercomputers

The researchers utilized GENREG, a well-established serial generator for regular graphs, and re-engineered it for distributed-memory environments using the Message Passing Interface (MPI).

Dynamic Task Scheduling

Graph generation is inherently unbalanced; different branches of the search tree vary wildly in computational depth. To address this, the team implemented a master-worker framework. A master node adaptively dispatches sub-tasks—decomposed into 50,000 to 200,000 units for order 23—to a pool of workers, ensuring high CPU utilization across thousands of cores.

Multi-Cluster Execution

The computation was distributed across three distinct supercomputing clusters:

  • SeaWulf (Stony Brook University, USA)
  • Tianhe-1 (National Supercomputer Center in Tianjin, China)
  • IBM Quinde (Escuela Politécnica Nacional, Ecuador)

This "opportunistic" approach leveraged fragmented resources across international borders, totaling nearly 100 core-years of computation.

Results and Discussion

The primary achievement is the expansion of the OEIS sequence A006820. The exact number of connected 4-regular graphs of order 23 was determined to be 429,668,180,677,439.

Table of quartic graph counts for orders 5 through 23, highlighting the new record.

Performance Insights

The study revealed significant performance variations between hardware architectures. Intel Xeon Gold processors in the SeaWulf cluster achieved a core speed of 178,000 graphs per second, nearly triple the 56,000 graphs per second observed on IBM Power8 cores. Scalability tests showed the framework could effectively utilize up to 3,000 cores before the single master node became a communication bottleneck.

Discovery of Optimal Topologies

Beyond the raw count, the search identified 56 specific 3-regular graphs of order 32 with absolute minimum ASPL. These "optimal" graphs provide superior network efficiency compared to standard topologies used in contemporary Beowulf clusters.

Visual representations of (32,3)-optimal and (32,4)-optimal regular graphs.

Conclusion

By successfully enumerating 4-regular graphs of order 23, this research demonstrates the power of adapting classical algorithms for modern parallel architectures. The discovery of new optimal topologies provides a practical path forward for designing lower-latency interconnection networks. Future work will focus on multi-level scheduling to overcome current master-node bottlenecks, potentially pushing the frontier to order 24 and beyond.

Summary updated

Abstract

We broke a record, set 8 years ago, in the enumeration of non-isomorphic regular graphs by expanding the sequence of A006820 in OEIS, to achieve the number for 4-regular graphs of order 23 as 429,668,180,677,439, while discovering serval optimal regular graphs with minimum diameters. The number of 4-regular graphs and the optimal graphs, extremely time-consuming to calculate, result from a method we adapt from GENREG, a classical regular graph generator, to fit for supercomputers' strengths of using thousands of processor cores.
BibTeX
@misc{xu2019new,
  author = {Zhipeng Xu and Xiaolong Huang and Fabián Jiménez and Yuefan Deng},
  title = {{A new record of enumeration of regular graphs by parallel processing}},
  year = {2019},
  eprint = {1907.12455},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1907.12455},
}
Figure