jeffdoesmath/graph-burning

Graph Burning: GPU-Accelerated Computation

GPU-accelerated verification of the Burning Number Conjecture and symbolic regression discovery of burning number formulas.

Key Results

• Conjecture verified for all connected graphs on n ≤ 12 vertices (165 billion graphs)
• PySR v1 formula: b(G) = ⌈√(n − Δ + 2)⌉ — exact for 99.996% of graphs tested
• PySR v2 formulas (diameter-aware, trained on n=2..2000):
  • Standard fit: ⌈√(n/Δ) + 0.81⌉
  • Upper bound: ⌈log(n)/√Δ + √n/(√n/⌈avg_dist⌉ + 1.09)⌉ (12/273,958 violations)
• SNAP networks: ego-Facebook (n=4,039, b≤4), ca-HepPh (n=11,204, b≤7)

Contents

File	Description
graph_burning/	GPU kernels (BFS, APSP, exact solver, heuristic) with CPU fallbacks
scripts/	Pipeline scripts: PySR training, SNAP analysis, verification
tests/	pytest suite validating against known burning numbers
pysr_v2_dataset.npz	Training data: 273K+ graphs, n=2..2000, 8 graph families
pysr_v2_standard.pkl	PySR v2 standard fit model
pysr_v2_upper.pkl	PySR v2 upper bound model
pysr_dataset.npz	PySR v1 training data (n≤10)
pysr_model.pkl	PySR v1 model
snap_results.json	SNAP network burning number results
verification_fast.log	Conjecture verification log (n≤12)
outputs/	Raw PySR output directories (4 runs)

Stack

• Python + Numba CUDA (GPU kernels)
• PySR (symbolic regression)
• nauty/geng (graph enumeration)
• Target hardware: NVIDIA A10/H100

Usage

pip install -r requirements.txt
python -m pytest tests/ -v
python scripts/run_pysr_v2.py --max-n 9 --iters 400

References

• Bonato, Janssen, Roshanbin (2016) — Burning Number Conjecture
• Bastide et al. (2022) — Improved bounds
• Land & Lu (2016) — Burning number of trees