List-homomorphism problems on graphs and arc consistency
From MaRDI portal
Publication:393914
DOI10.1016/j.disc.2013.07.018zbMath1281.05069MaRDI QIDQ393914
Adrien Lemaître, Benoit Larose
Publication date: 24 January 2014
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2013.07.018
arc-consistency; list-homomorphism problems; retraction problems; symmetric Datalog; totally symmetric operations
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C15: Coloring of graphs and hypergraphs
05C20: Directed graphs (digraphs), tournaments
Related Items
Unnamed Item, Algebra and the Complexity of Digraph CSPs: a Survey, Complexity of \(C_k\)-coloring in hereditary classes of graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Reflexive digraphs with near unanimity polymorphisms
- Absolute reflexive retracts and absolute bipartite retracts
- The complexity of the list homomorphism problem for graphs
- Universal algebra and hardness results for constraint satisfaction problems
- Circular-arc graphs with clique cover number two
- Majority constraints have bounded pathwidth duality
- Approximation of Minimum Cost Homomorphisms
- A polynomial-time algorithm for near-unanimity graphs
- Graphs Admitting $k$-NU Operations. Part 2: The Irreflexive Case
- Directed st-Connectivity Is Not Expressible in Symmetric Datalog
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Bi‐arc graphs and the complexity of list homomorphisms
- Constraint Satisfaction Problems of Bounded Width
- Classifying the Complexity of Constraints Using Finite Algebras
- Computational Complexity
- A Characterisation of First-Order Constraint Satisfaction Problems
- Recent Results on the Algebraic Approach to the CSP
- Dualities for Constraint Satisfaction Problems
