A combinatorial constraint satisfaction problem dichotomy classification conjecture

DOI10.1016/j.ejc.2009.02.007zbMath1187.68250OpenAlexW2017724352WikidataQ123137047 ScholiaQ123137047MaRDI QIDQ1041203

Mark H. Siggers, Jaroslav Nešetřil, László Zádori

Publication date: 1 December 2009

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejc.2009.02.007

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

In praise of homomorphisms ⋮ A strong Mal'cev condition for locally finite varieties omitting the unary type ⋮ A new line of attack on the dichotomy conjecture ⋮ Constraint satisfaction problems over semilattice block Mal'tsev algebras ⋮ \(H\)-coloring degree-bounded (acyclic) digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Colouring, constraint satisfaction, and complexity
• A strong Mal'cev condition for locally finite varieties omitting the unary type
• \(H\)-coloring dichotomy revisited
• List homomorphisms of graphs with bounded degrees
• Existence theorems for weakly symmetric operations
• Dichotomy for bounded degree \(H\)-colouring
• On the complexity of H-coloring
• On colorings of graphs without short cycles
• On the algebraic structure of combinatorial problems
• On sparse graphs with given colorings and homomorphisms.
• Networks of constraints: Fundamental properties and applications to picture processing
• Constraints, MMSNP and expander relational structures
• Closed systems of functions and predicates
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems
• Combinatorial Proof that Subprojective Constraint Satisfaction Problems are NP-Complete
• On highly ramsey infinite graphs
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The NP-Completeness of Edge-Coloring
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Closure properties of constraints
• The Complexity of the Extendibility Problem for Finite Posets
• Classifying the Complexity of Constraints Using Finite Algebras
• The complexity of satisfiability problems
• Principles and Practice of Constraint Programming – CP 2003
• Colorings and homomorphisms of degenerate and bounded degree graphs

This page was built for publication: A combinatorial constraint satisfaction problem dichotomy classification conjecture