2026-07-23T08:19:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23893 2025-11-12T13:11:07Z ddc:004 open_access

BFS-Based Canonical Codes for Generating Graphs with Constraint Programming Peng, Xiao Solnon, Christine Graph Generation Automorphisms Symmetry Breaking We consider the problem of generating all graphs that satisfy some given additional constraints (on vertex degrees, or cycle lengths, for example). Most previous works have proposed to generate canonical codes associated with adjacency matrices. In this paper, we consider canonical codes based on Breadth First Search (BFS), and we show how to generate them with Constraint Programming (CP): we introduce a set of basic constraints that must be satisfied by all canonical codes, thus breaking many symmetries, and we introduce a global constraint to break other symmetries. We illustrate the interest of our approach on connected claw-free cubic graphs, and show that it outperforms state-of-the-art CP and SAT Modulo Theory (SMT) approaches. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xiao Peng and Christine Solnon 2025 Is Part Of LIPIcs, Volume 340, 31st International Conference on Principles and Practice of Constraint Programming (CP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CP.2025.32 urn:nbn:de:0030-drops-238935 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2025.32 eng https://creativecommons.org/licenses/by/4.0/legalcode