A Characterisation of First-Order Constraint Satisfaction Problems

Benoit Larose; Cynthia Loten; Claude Tardif

doi:10.2168/LMCS-3(4:6)2007

Benoit Larose ; Cynthia Loten ; Claude Tardif - A Characterisation of First-Order Constraint Satisfaction Problems

lmcs:1097 - Logical Methods in Computer Science, November 6, 2007, Volume 3, Issue 4 - https://doi.org/10.2168/LMCS-3(4:6)2007

A Characterisation of First-Order Constraint Satisfaction ProblemsArticle

Authors: Benoit Larose ; Cynthia Loten ; Claude Tardif

We describe simple algebraic and combinatorial characterisations of finite relational core structures admitting finitely many obstructions. As a consequence, we show that it is decidable to determine whether a constraint satisfaction problem is first-order definable: we show the general problem to be NP-complete, and give a polynomial-time algorithm in the case of cores. A slight modification of this algorithm provides, for first-order definable CSP's, a simple poly-time algorithm to produce a solution when one exists. As an application of our algebraic characterisation of first order CSP's, we describe a large family of L-complete CSP's.

https://doi.org/10.2168/LMCS-3(4:6)2007

Source: arXiv.org:0707.2562

Volume: Volume 3, Issue 4

Secondary volumes: Selected Papers of the 21st IEEE Symposium on Logic in Computer Science (LICS 2006)

Published on: November 6, 2007

Imported on: March 2, 2007

Keywords: Computer Science - Logic in Computer Science, Computer Science - Computational Complexity, F.4.1

Licence: arXiv.org - Assumed non-exclusive license to distribute

Funding:

Source : OpenAIRE Graph

Funder: Natural Sciences and Engineering Research Council of Canada

Classifications

Mathematics Subject Classification 2020¹

Sources:

[1] zbMATH Open.

Bibliographic References

29 Documents citing this article

Libor Barto;Silvia Butti;Victor Dalmau, 2025, The Sherali–Adams and Weisfeiler–Leman Hierarchies in (Promise Valued) Constraint Satisfaction Problems, ACM Transactions on Computation Theory, 18, 1, pp. 1-37, 10.1145/3756323, https://doi.org/10.1145/3756323.

Andrei Krokhin;Jakub Opršal;Marcin Wrochna;Stanislav Živný, 2023, Topology and Adjunction in Promise Constraint Satisfaction, arXiv (Cornell University), 52, 1, pp. 38-79, 10.1137/20m1378223, http://arxiv.org/abs/2003.11351.

Balder Ten Cate;Victor Dalmau;Maurice Funk;Carsten Lutz, 2023, Extremal Fitting Problems for Conjunctive Queries, UvA-DARE (University of Amsterdam), pp. 89-98, 10.1145/3584372.3588655, https://handle.uba.uva.nl/personal/pure/en/publications/extremal-fitting-problems-for-conjunctive-queries(e1ae3470-3b5d-4be6-90bb-5907177977f4).html.

Olga Gerasimova;Stanislav Kikot;Agi Kurucz;Vladimir Podolskii;Michael Zakharyaschev, 2022, A tetrachotomy of ontology-mediated queries with a covering axiom, Artificial Intelligence, 309, pp. 103738, 10.1016/j.artint.2022.103738, https://doi.org/10.1016/j.artint.2022.103738.

Butti, Silvia;Dalmau, Victor, 2021, Fractional Homomorphism, Weisfeiler-Leman Invariance, and the Sherali-Adams Hierarchy for the Constraint Satisfaction Problem, DROPS (Schloss Dagstuhl – Leibniz Center for Informatics), 10.4230/lipics.mfcs.2021.27, https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.27.

Raimundo Briceño;Andrei Bulatov;Víctor Dalmau;Benoît Larose, 2020, Dismantlability, connectedness, and mixing in relational structures, arXiv (Cornell University), 147, pp. 37-70, 10.1016/j.jctb.2020.10.001, http://arxiv.org/abs/1901.04398.

Andrei A. Bulatov, 2018, Constraint satisfaction problems, ACM SIGLOG News, 5, 4, pp. 4-24, 10.1145/3292048.3292050.

Benoit Larose;Mark Siggers, 2018, NU Polymorphisms on Reflexive Digraphs, SIAM Journal on Discrete Mathematics, 32, 1, pp. 728-749, 10.1137/16m110527x.

Benoît Larose;Barnaby Martin;Daniël Paulusma, 2018, Surjective H-Colouring over Reflexive Digraphs, Durham Research Online (Durham University), 11, 1, pp. 1-21, 10.1145/3282431, http://dro.dur.ac.uk/24227/.

Andrei A. Bulatov, 2017, A Dichotomy Theorem for Nonuniform CSPs, arXiv (Cornell University), pp. 319-330, 10.1109/focs.2017.37, http://arxiv.org/abs/1703.03021.

Lucy Ham, 2017, Relativised Homomorphism Preservation at the Finite Level, Studia Logica, 105, 4, pp. 761-786, 10.1007/s11225-017-9710-7.

Victor Dalmau;Laszlo Egri;Pavol Hell;Benoit Larose;Arash Rafiey, 2015, Descriptive Complexity of List H-Coloring Problems in Logspace: A Refined Dichotomy, 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science, pp. 487-498, 10.1109/lics.2015.52.

Meghyn Bienvenu;Balder Ten Cate;Carsten Lutz;Frank Wolter, 2014, Ontology-Based Data Access, ACM Transactions on Database Systems, 39, 4, pp. 1-44, 10.1145/2661643.

Benoît Larose;Adrien Lemaître, 2013, List-homomorphism problems on graphs and arc consistency, Discrete Mathematics, 313, 22, pp. 2525-2537, 10.1016/j.disc.2013.07.018.

Pavol Hell, 2013, Graph partitions with prescribed patterns, European Journal of Combinatorics, 35, pp. 335-353, 10.1016/j.ejc.2013.06.043.

Barnaby Martin, 2011, Low-level dichotomy for quantified constraint satisfaction problems, Information Processing Letters, 111, 20, pp. 999-1003, 10.1016/j.ipl.2011.07.010, https://doi.org/10.1016/j.ipl.2011.07.010.

Cynthia Loten;Claude Tardif, 2011, Near-Unanimity Polymorphisms on Structures with Finite Duality, SIAM Journal on Discrete Mathematics, 25, 2, pp. 490-496, 10.1137/080731177.

László Egri;Andrei Krokhin;Benoit Larose;Pascal Tesson, 2011, The Complexity of the List Homomorphism Problem for Graphs, Theory of Computing Systems, 51, 2, pp. 143-178, 10.1007/s00224-011-9333-8.

Manuel Bodirsky;Daniel Král’, 2011, Limit Behavior of Locally Consistent Constraint Satisfaction Problems, SIAM Journal on Discrete Mathematics, 25, 2, pp. 916-933, 10.1137/060667591.

Cynthia Loten, 2010, Absolute retracts and varieties generated by chordal graphs, Discrete Mathematics, 310, 10-11, pp. 1507-1519, 10.1016/j.disc.2009.08.013.

Manuel Bodirsky;Martin Hils;Barnaby Martin, 2010, On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction, 2010 25th Annual IEEE Symposium on Logic in Computer Science, 117, pp. 90-99, 10.1109/lics.2010.13.

Andrei A. Bulatov;Andrei Krokhin;Benoit Larose, 2008, Dualities for Constraint Satisfaction Problems, Durham Research Online (Durham University), pp. 93-124, 10.1007/978-3-540-92800-3_5, https://durham-repository.worktribe.com/output/1661748.

Catarina Carvalho;Víctor Dalmau;Andrei Krokhin, 2008, Caterpillar Duality for Constraint Satisfaction Problems, Durham Research Online (Durham University), pp. 307-316, 10.1109/lics.2008.19, https://durham-repository.worktribe.com/output/1161739.

Cynthia Loten;Claude Tardif, 2008, Majority functions on structures with finite duality, European Journal of Combinatorics, 29, 4, pp. 979-986, 10.1016/j.ejc.2007.11.007.

Jaroslav NeŠetřil;Patrice Ossona De Mendez, 2008, Structural Properties of Sparse Graphs, Bolyai Society mathematical studies, pp. 369-426, 10.1007/978-3-540-85221-6_13.

Pavol Hell;Jaroslav Nešetřil, 2008, Colouring, constraint satisfaction, and complexity, Computer Science Review, 2, 3, pp. 143-163, 10.1016/j.cosrev.2008.10.003.

Phokion G. Kolaitis;Moshe Y. Vardi, 2008, A Logical Approach to Constraint Satisfaction, Lecture notes in computer science, pp. 125-155, 10.1007/978-3-540-92800-3_6.

Víctor Dalmau;Andrei Krokhin, 2008, Majority constraints have bounded pathwidth duality, Durham Research Online (Durham University), 29, 4, pp. 821-837, 10.1016/j.ejc.2007.11.020, https://durham-repository.worktribe.com/output/1554984.

Jan Foniok;Jaroslav Nešetřil;Claude Tardif, 2006, Generalised Dualities and Finite Maximal Antichains, Lecture notes in computer science, pp. 27-36, 10.1007/11917496_3.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 3344 times.

This article's PDF has been downloaded 581 times.