List-homomorphism problems on graphs and arc consistency

DOI10.1016/j.disc.2013.07.018zbMath1281.05069OpenAlexW2076955343MaRDI 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

zbMATH Keywords

arc-consistencylist-homomorphism problemsretraction problemssymmetric Datalogtotally symmetric operations

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

Related Items (3)

Complexity of \(C_k\)-coloring in hereditary classes of graphs ⋮ Algebra and the Complexity of Digraph CSPs: a Survey ⋮ Unnamed Item

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

This page was built for publication: List-homomorphism problems on graphs and arc consistency