SAT-Based Local Search for Plane Subgraph Partitions

Schidler, André

doi:10.4230/LIPIcs.SoCG.2022.74

Record link:

http://hdl.handle.net/20.500.12708/150308

Title:

SAT-Based Local Search for Plane Subgraph Partitions

Citation:

Schidler, A. (2022). SAT-Based Local Search for Plane Subgraph Partitions. In X. Goaoc & M. Kerber (Eds.), 38th International Symposium on Computational Geometry (SoCG 2022) (pp. 1–8). Schloss Dagstuhl --Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2022.74

CatalogPlus:

AC17203613

Publisher DOI:

10.4230/LIPIcs.SoCG.2022.74

Publication Type:

Inproceedings - Full-Paper Contribution

Language:

English

Authors:

Schidler, André

Organisational Unit:

E192-01 - Forschungsbereich Algorithms and Complexity

Published in:

38th International Symposium on Computational Geometry (SoCG 2022)

ISBN:

978-3-95977-227-3

Volume:

224

DOI of the book:

10.4230/LIPIcs.SoCG.2022

Date (published):

1-Jun-2022

Event name:

38th International Symposium on Computational Geometry (SoCG 2022)

Event date:

7-Jun-2022 - 10-Jun-2022

Event place:

Berlin, Germany

Number of Pages:

Publisher:

Schloss Dagstuhl --Leibniz-Zentrum für Informatik, Dagstuhl

Keywords:

graph coloring; large neighborhood search; local improvement; logic; plane subgraphs; SAT; SLIM

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.

Project title:

SAT-Basierende lokale Verbesserungsmethoden: P32441-N35 (FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF))
Revealing and Utilizing the Hidden Structure for Solving Hard Problems in AI: ICT19-065 (WWTF Wiener Wissenschafts-, Forschu und Technologiefonds)

Project (external):

Austrian Science Fund (FWF)

Project ID:

W1255

Link (external):

https://github.com/ASchidler/coloring
https://doi.org/10.5281/zenodo.6352601

Research Areas:

Logic and Computation: 100%

Science Branch:

1020 - Informatik: 80%
1010 - Mathematik: 20%

License:

CC BY 4.0