Manuel Bodirsky
Constraint satisfaction problems for reducts of homogeneous graphs
Bodirsky, Manuel; Martin, Barnaby; Pinsker, Michael; Pongracz, Andras
Authors
Abstract
For $n\geq 3$, let $(H_n, E)$ denote the $n$th Henson graph, i.e., the unique countable homogeneous graph with exactly those finite graphs as induced subgraphs that do not embed the complete graph on $n$ vertices. We show that for all structures $\Gamma$ with domain $H_n$ whose relations are first-order definable in $(H_n,E)$ the constraint satisfaction problem for $\Gamma$ either is in P or is NP-complete. We moreover show a similar complexity dichotomy for all structures whose relations are first-order definable in a homogeneous graph whose reflexive closure is an equivalence relation. Together with earlier results, in particular for the random graph, this completes the complexity classification of constraint satisfaction problems of structures first-order definable in countably infinite homogeneous graphs: all such problems are either in P or NP-complete.
Citation
Bodirsky, M., Martin, B., Pinsker, M., & Pongracz, A. (2019). Constraint satisfaction problems for reducts of homogeneous graphs. SIAM Journal on Computing, 48(4), 1224-1264. https://doi.org/10.1137/16m1082974
Journal Article Type | Article |
---|---|
Acceptance Date | May 2, 2019 |
Online Publication Date | Jul 18, 2019 |
Publication Date | Jan 1, 2019 |
Deposit Date | Jul 2, 2019 |
Publicly Available Date | Oct 8, 2019 |
Journal | SIAM Journal on Computing |
Print ISSN | 0097-5397 |
Electronic ISSN | 1095-7111 |
Publisher | Society for Industrial and Applied Mathematics |
Peer Reviewed | Peer Reviewed |
Volume | 48 |
Issue | 4 |
Pages | 1224-1264 |
DOI | https://doi.org/10.1137/16m1082974 |
Files
Published Journal Article
(552 Kb)
PDF
Copyright Statement
© 2019 Society for Industrial and Applied Mathematics.
You might also like
The lattice and semigroup structure of multipermutations
(2021)
Journal Article
Surjective H-Colouring over reflexive digraphs
(2018)
Journal Article
On the Complexity of the Model Checking Problem
(2018)
Journal Article
Surjective H-colouring: New hardness results
(2018)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search