Improved Exact Algorithm for Finding a Maximum Exploratory Equivalent Partition

Abstract

An exploratory equivalent partition (EE partition) of a graph G with nontrivial automorphisms is a partition of its vertex set that can be directly translated into a set of constraints to speed up the search for occurrences of G in an arbitrary host graph. The maximum EE partition problem is to find an EE partition leading to the greatest speedup. However, this problem is NP-hard and the naïve algorithm is only practicable for small symmetry-rich graphs. In this paper, we propose a series of improvements based on computational group theory that vastly increase the algorithm’s range of practicability. For example, the improved algorithm spends less time on the 10-hypercube graph (1024 vertices, 5120 edges, ≈3.7 × 109 automorphisms) than the naïve algorithm does on the 4-hypercube graph (16 vertices, 32 edges, 384 automorphisms). We prove that all improvements maintain the algorithm’s correctness and confirm their contribution to the speed of execution through extensive experimentation.