The complexity of the list homomorphism problem for graphs
DOI10.1007/S00224-011-9333-8zbMATH Open1322.68100OpenAlexW2028556486MaRDI QIDQ693060FDOQ693060
Authors: László Egri, Benoît Larose, Pascal Tesson, Andrei 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/
Recommendations
Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)
Cites Work
- Title not available (Why is that?)
- Computational Complexity
- Existence theorems for weakly symmetric operations
- Linear-time recognition of circular-arc graphs
- Title not available (Why is that?)
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Classifying the Complexity of Constraints Using Finite Algebras
- The complexity of satisfiability problems
- Recent Results on the Algebraic Approach to the CSP
- 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
- A Characterisation of First-Order Constraint Satisfaction Problems
- Dualities for Constraint Satisfaction Problems
- Bounded width problems and algebras
- Universal algebra and hardness results for constraint satisfaction problems
- List homomorphisms and circular arc graphs
- Constraint Satisfaction Problems of Bounded Width
- Near-Unanimity Functions and Varieties of Reflexive Graphs
- Bi‐arc graphs and the complexity of list homomorphisms
- Characterizations for co-graphs defined by restricted NLC-width or clique-width operations
- Majority constraints have bounded pathwidth duality
- A Logical Approach to Constraint Satisfaction
- A Subalgebra Intersection Property for Congruence Distributive Varieties
- Linear Datalog and Bounded Path Duality of Relational Structures
- CSP duality and trees of bounded pathwidth
- The complexity of satisfiability problems: Refining Schaefer's theorem
Cited In (25)
- List homomorphisms and circular arc graphs
- List-homomorphism problems on graphs and arc consistency
- A generalization of the theorem of Lekkerkerker and Boland
- Complexity of homomorphisms to direct products of graphs
- Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy
- Descriptive complexity of list H-coloring problems in logspace: a refined dichotomy
- The complexity of tropical graph homomorphisms
- Sparsification lower bounds for list \(H\)-coloring
- List homomorphisms of graphs with bounded degrees
- Bi‐arc graphs and the complexity of list homomorphisms
- Title not available (Why is that?)
- Title not available (Why is that?)
- The parameterised complexity of list problems on graphs of bounded treewidth
- Parameterized algorithms for min-max multiway cut and list digraph homomorphism
- Testing list \(H\)-homomorphisms
- The complexity of the list homomorphism problem for graphs
- Constraint satisfaction problems for reducts of homogeneous graphs
- Algebra and the complexity of digraph CSPs: a survey
- Title not available (Why is that?)
- Complexity of correspondence \(H\)-colourings
- Vertex ordering with precedence constraints
- Constraint satisfaction problems for reducts of homogeneous graphs
- Multilist layering: Complexity and applications
- List homomorphism: beyond the known boundaries
- List H-coloring a graph by removing few vertices
This page was built for publication: The complexity of the list homomorphism problem for graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q693060)
