Document Open Access Logo

SAT-Based Local Search for Plane Subgraph Partitions (CG Challenge)

Author André Schidler

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2022.74.pdf
  • Filesize: 4.2 MB
  • 8 pages

Document Identifiers

Author Details

André Schidler
  • TU Wien, Austria

Funding

FWF (P32441, W1255) and the WWTF (ICT19-065).

Cite As Get BibTex

André Schidler. SAT-Based Local Search for Plane Subgraph Partitions (CG Challenge). In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 74:1-74:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.SoCG.2022.74

Abstract

The Partition into Plane Subgraphs Problem (PPS) asks to partition the edges of a geometric graph with straight line segments into as few classes as possible, such that the line segments within a class do not cross. We discuss our approach GC-SLIM: a local search method that views PPS as a graph coloring problem and tackles it with a new and unique combination of propositional satisfiability (SAT) and tabu search, achieving the fourth place in the 2022 CG:SHOP Challenge.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • graph coloring
  • plane subgraphs
  • SAT
  • logic
  • SLIM
  • local improvement
  • large neighborhood search

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Cadical. http://fmv.jku.at/cadical/. Accessed: 2022-02-20.
  2. Glucose. https://www.labri.fr/perso/lsimon/glucose/. Accessed: 2022-02-20.
  3. Olivier Bailleux and Yacine Boufkhad. Efficient CNF encoding of boolean cardinality constraints. In Francesca Rossi, editor, Principles and Practice of Constraint Programming - CP 2003, 9th International Conference, CP 2003, Kinsale, Ireland, September 29 - October 3, 2003, Proceedings, volume 2833 of Lecture Notes in Computer Science, pages 108-122. Springer, 2003. URL: https://doi.org/10.1007/978-3-540-45193-8_8.
  4. Armin Biere, Katalin Fazekas, Mathias Fleury, and Maximillian Heisinger. CaDiCaL, Kissat, Paracooba, Plingeling and Treengeling entering the SAT Competition 2020. In Tomas Balyo, Nils Froleyks, Marijn Heule, Markus Iser, Matti Järvisalo, and Martin Suda, editors, Proc. of SAT Competition 2020 - Solver and Benchmark Descriptions, volume B-2020-1 of Department of Computer Science Report Series B, pages 51-53. University of Helsinki, 2020. Google Scholar
  5. Ivo Blöchliger and Nicolas Zufferey. A graph coloring heuristic using partial solutions and a reactive tabu scheme. Comput. Oper. Res., 35(3):960-975, 2008. URL: https://doi.org/10.1016/j.cor.2006.05.014.
  6. Daniel Brélaz. New methods to color the vertices of a graph. Commun. ACM, 22(4):251-256, April 1979. Google Scholar
  7. Loïc Crombez, Guilherme D. da Fonseca, Yan Gerard, and Aldo Gonzalez-Lorenzo. Shadoks approach to minimum partition into plane subgraphs. In Symposium on Computational Geometry (SoCG), pages 71:1-71:8, 2022. Google Scholar
  8. Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, and Stefan Schirra. Minimum partition into plane subgraphs: The CG: SHOP Challenge 2022. CoRR, abs/2203.07444, 2022. URL: http://arxiv.org/abs/2203.07444.
  9. Johannes K. Fichte, Neha Lodha, and Stefan Szeider. SAT-based local improvement for finding tree decompositions of small width. In Proceedings of SAT 2017, volume 10491 of Lecture Notes in Computer Science, pages 401-411. Springer Verlag, 2017. Google Scholar
  10. Florian Fontan, Pascal Lafourcade, Luc Libralesso, and Benjamin Momège. Local search with weighting schemes for the CG:SHOP 2022 competition. In Symposium on Computational Geometry (SoCG), pages 73:1-73:7, 2022. Google Scholar
  11. Emmanuel Hebrard and George Katsirelos. A hybrid approach for exact coloring of massive graphs. In Louis-Martin Rousseau and Kostas Stergiou, editors, Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 16th International Conference, CPAIOR 2019, Thessaloniki, Greece, June 4-7, 2019, Proceedings, volume 11494 of Lecture Notes in Computer Science, pages 374-390. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-19212-9_25.
  12. Jinkun Lin, Shaowei Cai, Chuan Luo, and Kaile Su. A reduction based method for coloring very large graphs. In Carles Sierra, editor, Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017, pages 517-523. ijcai.org, 2017. URL: https://doi.org/10.24963/ijcai.2017/73.
  13. Neha Lodha, Sebastian Ordyniak, and Stefan Szeider. A SAT approach to branchwidth. In Carles Sierra, editor, Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017, pages 4894-4898. ijcai.org, 2017. URL: https://doi.org/10.24963/ijcai.2017/689.
  14. Vaidyanathan Peruvemba Ramaswamy and Stefan Szeider. Learning fast-inference bayesian networks. Advances in Neural Information Processing Systems, 34, 2021. Google Scholar
  15. Vaidyanathan Peruvemba Ramaswamy and Stefan Szeider. Turbocharging treewidth-bounded Bayesian network structure learning. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pages 3895-3903. AAAI Press, 2021. Google Scholar
  16. André Schidler and Stefan Szeider. SAT-based decision tree learning for large data sets. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pages 3904-3912. AAAI Press, 2021. URL: https://ojs.aaai.org/index.php/AAAI/article/view/16509.
  17. Jack Spalding-Jamieson, Brandon Zhang, and Da Wei Zheng. Conflict-based local search for minimum partition into plane subgraphs. In Symposium on Computational Geometry (SoCG), pages 72:1-72:6, 2022. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact