Improved exact algorithm for finding a maximum exploratory equivalent partitionSikošek, Lovro (Avtor) Čibej, Uroš (Avtor) Mihelič, Jurij (Avtor) Fürst, Luka (Avtor) graph theoryexploratory equivalencesymmetryautomorphismisomorphismNP-hardcomputational group theoryAn 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 × 10$^9$ 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.20262026-10-01 12:08:37Članek v reviji189102sl