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.SEA.2022.18
URN: urn:nbn:de:0030-drops-165526
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16552/
Alferov, Vasily ;
de Oliveira Oliveira, Mateus
On the Satisfiability of Smooth Grid CSPs
Abstract
Many important NP-hard problems, arising in a wide variety of contexts, can be reduced straightforwardly to the satisfiability problem for CSPs whose underlying graph is a grid. In this work, we push forward the study of grid CSPs by analyzing, from an experimental perspective, a symbolic parameter called smoothness.
More specifically, we implement an algorithm that provably works in polynomial time on grids of polynomial smoothness. Subsequently, we compare our algorithm with standard combinatorial optimization techniques, such as SAT-solving and integer linear programming (ILP). For this comparison, we use a class of grid-CSPs encoding the pigeonhole principle. We demonstrate, empirically, that these CSPs have polynomial smoothness and that our algorithm terminates in polynomial time.
On the other hand, as strong evidence that the grid-like encoding is not destroying the essence of the pigeonhole principle, we show that the standard propositional translation of pigeonhole CSPs remains hard for state-of-the-art SAT solvers, such as minisat and glucose, and even to state-of-the-art integer linear-programming solvers, such as Coin-OR CBC.
BibTeX - Entry
@InProceedings{alferov_et_al:LIPIcs.SEA.2022.18,
author = {Alferov, Vasily and de Oliveira Oliveira, Mateus},
title = {{On the Satisfiability of Smooth Grid CSPs}},
booktitle = {20th International Symposium on Experimental Algorithms (SEA 2022)},
pages = {18:1--18:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-251-8},
ISSN = {1868-8969},
year = {2022},
volume = {233},
editor = {Schulz, Christian and U\c{c}ar, Bora},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16552},
URN = {urn:nbn:de:0030-drops-165526},
doi = {10.4230/LIPIcs.SEA.2022.18},
annote = {Keywords: Grid CSPs, Smoothness, SAT Solving, Linear Programming}
}
