License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2023.39
URN: urn:nbn:de:0030-drops-190760
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19076/
Zhang, Tianwei ;
Szeider, Stefan
Searching for Smallest Universal Graphs and Tournaments with SAT
Abstract
A graph is induced k-universal if it contains all graphs of order k as an induced subgraph. For over half a century, the question of determining smallest k-universal graphs has been studied. A related question asks for a smallest k-universal tournament containing all tournaments of order k.
This paper proposes and compares SAT-based methods for answering these questions exactly for small values of k. Our methods scale to values for which a generate-and-test approach isn't feasible; for instance, we show that an induced 7-universal graph has more than 16 vertices, whereas the number of all connected graphs on 16 vertices, modulo isomorphism, is a number with 23 decimal digits Our methods include static and dynamic symmetry breaking and lazy encodings, employing external subgraph isomorphism testing.
BibTeX - Entry
@InProceedings{zhang_et_al:LIPIcs.CP.2023.39,
author = {Zhang, Tianwei and Szeider, Stefan},
title = {{Searching for Smallest Universal Graphs and Tournaments with SAT}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {39:1--39:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-300-3},
ISSN = {1868-8969},
year = {2023},
volume = {280},
editor = {Yap, Roland H. C.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/19076},
URN = {urn:nbn:de:0030-drops-190760},
doi = {10.4230/LIPIcs.CP.2023.39},
annote = {Keywords: Constrained-based combinatorics, synthesis problems, symmetry breaking, SAT solving, subgraph isomorphism, tournament, directed graphs}
}
Keywords: |
|
Constrained-based combinatorics, synthesis problems, symmetry breaking, SAT solving, subgraph isomorphism, tournament, directed graphs |
Collection: |
|
29th International Conference on Principles and Practice of Constraint Programming (CP 2023) |
Issue Date: |
|
2023 |
Date of publication: |
|
22.09.2023 |
Supplementary Material: |
|
Software: https://doi.org/10.5281/zenodo.8147732 |