Options
An order out of nowhere : a new algorithm for infinite-domain CSPs
Citation Link: https://doi.org/10.15480/882.13172
Publikationstyp
Conference Paper
Date Issued
2024-07-02
Sprache
English
TORE-DOI
First published in
Number in series
297
Volume
297
Article Number
148
Citation
Leibniz International Proceedings in Informatics, LIPIcs 297: 148 (2024)
Contribution to Conference
Publisher DOI
Scopus ID
Publisher
Dagstuhl Publishing
ISBN
9783959773225
We consider the problem of satisfiability of sets of constraints in a given set of finite uniform hypergraphs. While the problem under consideration is similar in nature to the problem of satisfiability of constraints in graphs, the classical complexity reduction to finite-domain CSPs that was used in the proof of the complexity dichotomy for such problems cannot be used as a black box in our case. We therefore introduce an algorithmic technique inspired by classical notions from the theory of finite-domain CSPs, and prove its correctness based on symmetries that depend on a linear order that is external to the structures under consideration. Our second main result is a P/NP-complete complexity dichotomy for such problems over many sets of uniform hypergraphs. The proof is based on the translation of the problem into the framework of constraint satisfaction problems (CSPs) over infinite uniform hypergraphs. Our result confirms in particular the Bodirsky-Pinsker conjecture for CSPs of first-order reducts of some homogeneous hypergraphs. This forms a vast generalization of previous work by Bodirsky-Pinsker (STOC’11) and Bodirsky-Martin-Pinsker-Pongrácz (ICALP’16) on graph satisfiability.
Subjects
Constraint Satisfaction Problems
Hypergraphs
Polymorphisms
DDC Class
004: Computer Sciences
Publication version
publishedVersion
Loading...
Name
LIPIcs.ICALP.2024.148.pdf
Type
Main Article
Size
749.52 KB
Format
Adobe PDF