The complexity of the list homomorphism problem for graphs

DOI10.1007/s00224-011-9333-8zbMath1322.68100OpenAlexW2028556486MaRDI QIDQ693060

Pascal Tesson, László Egri, Benoit Larose, Andrei A. Krokhin

Publication date: 7 December 2012

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2010/2467/

zbMATH Keywords

computational complexityconstraint satisfaction problemDataloguniversal algebralist homomorphism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Testing list \(H\)-homomorphisms ⋮ Parameterized algorithms for min-max multiway cut and list digraph homomorphism ⋮ List-homomorphism problems on graphs and arc consistency ⋮ List homomorphism: beyond the known boundaries ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Algebra and the Complexity of Digraph CSPs: a Survey ⋮ List H-coloring a graph by removing few vertices

Cites Work

• Unnamed Item
• Unnamed Item
• Characterizations for co-graphs defined by restricted NLC-width or clique-width operations
• CSP duality and trees of bounded pathwidth
• Bounded width problems and algebras
• Existence theorems for weakly symmetric operations
• Universal algebra and hardness results for constraint satisfaction problems
• The complexity of satisfiability problems: Refining Schaefer's theorem
• Linear-time recognition of circular-arc graphs
• List homomorphisms and circular arc graphs
• Majority constraints have bounded pathwidth duality
• Near-Unanimity Functions and Varieties of Reflexive Graphs
• A Subalgebra Intersection Property for Congruence Distributive Varieties
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The structure of finite algebras
• 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
• Linear Datalog and Bounded Path Duality of Relational Structures
• Classifying the Complexity of Constraints Using Finite Algebras
• Computational Complexity
• The complexity of satisfiability problems
• A Characterisation of First-Order Constraint Satisfaction Problems
• Recent Results on the Algebraic Approach to the CSP
• Dualities for Constraint Satisfaction Problems
• A Logical Approach to Constraint Satisfaction