A symmetry-breaking node equivalence for pruning the search space in backtracking algorithms

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

We introduce a new equivalence on graphs, defined by its symmetry-breaking capability. We first present a framework for various backtracking search algorithms, in which the equivalence is used to prune the search tree. Subsequently, we define the equivalence and an optimization problem with the goal of finding an equivalence partition with the highest pruning potential. We also position the optimization problem into the computational-complexity hierarchy. In particular, we show that the verifier lies between P and NP-complete problems. Striving for a practical usability of the approach, we devise a heuristic method for general graphs and optimal algorithms for trees and cycles.

• Language: English
• Keywords: graph equivalence, symmetry breaking, backtracking, monomorphism search, search tree pruning, graph algorithm
• 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: 2019
• Number of pages: 26 str.
• Numbering: Vol. 11, iss. 10, art. 1300
• PID: 20.500.12556/RUL-133142
• UDC: 004:519.17
• ISSN on article: 2073-8994
• DOI: 10.3390/sym11101300
• COBISS.SI-ID: 1538408387
• Publication date in RUL: 12.11.2021

Record is a part of a journal

• Title: Symmetry
• Shortened title: Symmetry
• Publisher: Molecular Diversity Preservation International
• 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.
• Licensing start date: 15.10.2019

Secondary language

• Language: Slovenian
• Keywords: grafna ekvivalenca, razbijanje simetrij, sestopanje, iskanje monomorfizmov, rezanje iskalnega drevesa, algoritem na grafih