Article

The Dichotomy for Conservative Constraint Satisfaction Problems Revisited

Author:

Libor BartoAuthors Info & Claims

LICS '11: Proceedings of the 2011 IEEE 26th Annual Symposium on Logic in Computer Science

Pages 301 - 310

https://doi.org/10.1109/LICS.2011.25

Published: 21 June 2011 Publication History

Abstract

A central open question in the study of non-uniform constraint satisfaction problems (CSPs) is the dichotomy conjecture of Feder and Vardi stating that the CSP over a fixed constraint language is either NP-complete, or tractable. One of the main achievements in this direction is a result of Bulatov (LICS'03) confirming the dichotomy conjecture for conservative CSPs, that is, CSPs over constraint languages containing all unary relations. Unfortunately, the proof is very long and complicated, and therefore hard to understand even for a specialist. This paper provides a short and transparent proof.

Cited By

View all

Focke JMarx DRzążewski P(2024)Counting List Homomorphisms from Graphs of Bounded Treewidth: Tight Complexity BoundsACM Transactions on Algorithms10.1145/364081420:2(1-32)Online publication date: 13-Feb-2024
https://dl.acm.org/doi/10.1145/3640814
Wijsen J(2019)Foundations of Query Answering on Inconsistent DatabasesACM SIGMOD Record10.1145/3377391.337739348:3(6-16)Online publication date: 20-Dec-2019
https://dl.acm.org/doi/10.1145/3377391.3377393
Wrona M(2019)The Complexity of Minimal Inference Problem for Conservative Constraint LanguagesACM Transactions on Computational Logic10.1145/330141020:2(1-35)Online publication date: 18-Feb-2019
https://dl.acm.org/doi/10.1145/3301410
Show More Cited By

The Dichotomy for Conservative Constraint Satisfaction Problems Revisited
1. Theory of computation
  1. Logic

Recommendations

Complexity of conservative constraint satisfaction problems

In a constraint satisfaction problem (CSP), the aim is to find an assignment of values to a given set of variables, subject to specified constraints. The CSP is known to be NP-complete in general. However, certain restrictions on the form of the allowed ...
A dichotomy theorem for constraint satisfaction problems on a 3-element set

The Constraint Satisfaction Problem (CSP) provides a common framework for many combinatorial problems. The general CSP is known to be NP-complete; however, certain restrictions on a possible form of constraints may affect the complexity and lead to ...
Approximate counting for complex-weighted Boolean constraint satisfaction problems

Constraint satisfaction problems (or CSPs) have been extensively studied in, for instance, artificial intelligence, database theory, graph theory, and statistical physics. From a practical viewpoint, it is beneficial to approximately solve those CSPs. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

LICS '11: Proceedings of the 2011 IEEE 26th Annual Symposium on Logic in Computer Science

June 2011

379 pages

ISBN:9780769544120

Publisher

IEEE Computer Society

United States

Publication History

Published: 21 June 2011

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Focke JMarx DRzążewski P(2024)Counting List Homomorphisms from Graphs of Bounded Treewidth: Tight Complexity BoundsACM Transactions on Algorithms10.1145/364081420:2(1-32)Online publication date: 13-Feb-2024
https://dl.acm.org/doi/10.1145/3640814
Wijsen J(2019)Foundations of Query Answering on Inconsistent DatabasesACM SIGMOD Record10.1145/3377391.337739348:3(6-16)Online publication date: 20-Dec-2019
https://dl.acm.org/doi/10.1145/3377391.3377393
Wrona M(2019)The Complexity of Minimal Inference Problem for Conservative Constraint LanguagesACM Transactions on Computational Logic10.1145/330141020:2(1-35)Online publication date: 18-Feb-2019
https://dl.acm.org/doi/10.1145/3301410
Kirousis LKolaitis PLivieratos J(2019)Aggregation of Votes with Multiple Positions on Each IssueACM Transactions on Economics and Computation10.1145/32966757:1(1-25)Online publication date: 25-Jan-2019
https://dl.acm.org/doi/10.1145/3296675
Bulatov A(2018)Constraint satisfaction problemsACM SIGLOG News10.1145/3292048.32920505:4(4-24)Online publication date: 12-Nov-2018
https://dl.acm.org/doi/10.1145/3292048.3292050
Buln J(2018)On the complexity of H-coloring for special oriented treesEuropean Journal of Combinatorics10.1016/j.ejc.2017.10.00169:C(54-75)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1016/j.ejc.2017.10.001
Bulatov AAceto LIngólfsdóttir A(2017)Constraint satisfaction problems over semilattice block Mal'tsev algebrasProceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science10.5555/3329995.3330084(1-11)Online publication date: 20-Jun-2017
https://dl.acm.org/doi/10.5555/3329995.3330084
Wrona MAceto LIngólfsdóttir A(2017)The complexity of minimal inference problem for conservative constraint languagesProceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science10.5555/3329995.3330051(1-12)Online publication date: 20-Jun-2017
https://dl.acm.org/doi/10.5555/3329995.3330051
Carbonnel C(2016)The meta-problem for conservative Mal'tsev constraintsProceedings of the Thirtieth AAAI Conference on Artificial Intelligence10.5555/3016100.3016377(3376-3382)Online publication date: 12-Feb-2016
https://dl.acm.org/doi/10.5555/3016100.3016377
Jonsson P(2016)Finite unary relations and qualitative constraint satisfactionProceedings of the Twenty-second European Conference on Artificial Intelligence10.3233/978-1-61499-672-9-37(37-45)Online publication date: 29-Aug-2016
https://dl.acm.org/doi/10.3233/978-1-61499-672-9-37
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

Cited By

Recommendations

Complexity of conservative constraint satisfaction problems

A dichotomy theorem for constraint satisfaction problems on a 3-element set

Approximate counting for complex-weighted Boolean constraint satisfaction problems

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations