Improved exact algorithm for finding a maximum exploratory equivalent partition

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

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.

• Jezik: Angleški jezik
• Ključne besede: graph theory, exploratory equivalence, symmetry, automorphism, isomorphism, NP-hard, computational group theory
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Leto izida: 2026
• Št. strani: 39 str.
• Številčenje: Vol. 18, iss. 10, art. 1604
• PID: 20.500.12556/RUL-189102
• UDK: 519.17
• ISSN pri članku: 2073-8994
• DOI: 10.3390/sym18101604
• COBISS.SI-ID: 292700931
• Datum objave v RUL: 01.10.2026

Gradivo je del revije

• Naslov: Symmetry
• Skrajšan naslov: Symmetry
• Založnik: MDPI
• ISSN: 2073-8994
• COBISS.SI-ID: 517592345

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: teorija grafov, preiskovalna ekvivalenca, simetrija, avtomorfizem, izomorfizem, NP-težek, računska teorija grup