Breaking Symmetries from a Set-Covering Perspective

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21730%2F25%3A00387624" target="_blank" >RIV/68407700:21730/25:00387624 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/978-3-031-95973-8_11" target="_blank" >https://doi.org/10.1007/978-3-031-95973-8_11</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-031-95973-8_11" target="_blank" >10.1007/978-3-031-95973-8_11</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Breaking Symmetries from a Set-Covering Perspective

Popis výsledku v původním jazyce

We formalize symmetry breaking as a set-covering problem. For the case of breaking symmetries on graphs, a permutation covers a graph if applying it to the graph yields a smaller graph in a given order. Canonical graphs are those that cannot be made smaller by any permutation. A complete symmetry break is then a set of permutations that covers all non-canonical graphs. A complete symmetry break with a minimal number of permutations can be obtained by solving an optimal set-covering problem. The challenge is in the sizes of the corresponding set-covering problems and in how these can be tamed. The set-covering perspective on symmetry breaking opens up a range of new opportunities deriving from decades of studies on both precise and approximate techniques for this problem. Application of our approach leads to optimal LexLeader symmetry breaks for graphs of order as well as to partial symmetry breaks which improve on the state-of-the-art.

Název v anglickém jazyce

Breaking Symmetries from a Set-Covering Perspective

Popis výsledku anglicky

We formalize symmetry breaking as a set-covering problem. For the case of breaking symmetries on graphs, a permutation covers a graph if applying it to the graph yields a smaller graph in a given order. Canonical graphs are those that cannot be made smaller by any permutation. A complete symmetry break is then a set of permutations that covers all non-canonical graphs. A complete symmetry break with a minimal number of permutations can be obtained by solving an optimal set-covering problem. The challenge is in the sizes of the corresponding set-covering problems and in how these can be tamed. The set-covering perspective on symmetry breaking opens up a range of new opportunities deriving from decades of studies on both precise and approximate techniques for this problem. Application of our approach leads to optimal LexLeader symmetry breaks for graphs of order as well as to partial symmetry breaks which improve on the state-of-the-art.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2025

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Integration of Constraint Programming, Artificial Intelligence, and Operations Research 22nd International Conference, CPAIOR 2025, Melbourne, VIC, Australia, November 10–13, 2025, Proceedings, Part I

ISBN

978-3-031-95972-1

ISSN

0302-9743

e-ISSN

1611-3349

Počet stran výsledku

19

Strana od-do

169-187

Název nakladatele

Springer

Místo vydání

Cham

Místo konání akce

Melbourne

Datum konání akce

10. 11. 2025

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

001547301600011