Improved exact algorithm for finding a maximum exploratory equivalent partition

Sikošek, Lovro (author), Čibej, Uroš (author), Mihelič, Jurij (author), Fürst, Luka (author)

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 × 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.

• Language: English
• Keywords: graph theory, exploratory equivalence, symmetry, automorphism, isomorphism, NP-hard, computational group theory
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FRI - Faculty of Computer and Information Science
• Publication status: Published
• Publication version: Version of Record
• Year: 2026
• Number of pages: 39 str.
• Numbering: Vol. 18, iss. 10, art. 1604
• PID: 20.500.12556/RUL-189102
• UDC: 519.17
• ISSN on article: 2073-8994
• DOI: 10.3390/sym18101604
• COBISS.SI-ID: 292700931
• Publication date in RUL: 01.10.2026

Record is a part of a journal

• Title: Symmetry
• Shortened title: Symmetry
• Publisher: MDPI
• ISSN: 2073-8994
• COBISS.SI-ID: 517592345

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.

Secondary language

• Language: Slovenian
• Keywords: teorija grafov, preiskovalna ekvivalenca, simetrija, avtomorfizem, izomorfizem, NP-težek, računska teorija grup