Symmetry-Preserving Graph Compression

Exploiting symmetry is a well-established technique to eliminate redundant work in combinatorial solvers, yet it often incurs computational overhead that limits its practical impact. In particular, practical instances arising from applications are frequently large and give rise to graphs whose size becomes a major bottleneck for algorithms dealing with symmetry. We propose a method for symmetry-preserving graph compression that reduces graph size while preserving the symmetries of the original graph in a controlled way. Our approach identifies and merges equivalent vertex colors under conditions that guarantee the recoverability of all symmetries. We provide both a theoretical foundation and efficient practical criteria for such merges, show that computing optimal and approximately optimal compression is intractable, and introduce a linear-time, practical heuristic. Extensive experiments on a vast library of graphs demonstrate that our new technique achieves significant compression ratios. Implemented in the state-of-the-art symmetry detection tool dejavu, we achieve an overall speedup of 1.39, with large modern SAT and MIP benchmarks benefiting the most.