The complexity of the list homomorphism problem for graphs
From MaRDI portal
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)
Recommendations
Cites work
- scientific article; zbMATH DE number 3987347 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- A Characterisation of First-Order Constraint Satisfaction Problems
- A Logical Approach to Constraint Satisfaction
- A Subalgebra Intersection Property for Congruence Distributive Varieties
- Bi‐arc graphs and the complexity of list homomorphisms
- Bounded width problems and algebras
- CSP duality and trees of bounded pathwidth
- Characterizations for co-graphs defined by restricted NLC-width or clique-width operations
- Classifying the Complexity of Constraints Using Finite Algebras
- Computational Complexity
- Constraint Satisfaction Problems of Bounded Width
- Dualities for Constraint Satisfaction Problems
- Existence theorems for weakly symmetric operations
- Linear Datalog and Bounded Path Duality of Relational Structures
- 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
- 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 Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The complexity of satisfiability problems
- The complexity of satisfiability problems: Refining Schaefer's theorem
- The structure of finite algebras
- Universal algebra and hardness results for constraint satisfaction problems
Cited in
(24)- Constraint satisfaction problems for reducts of homogeneous graphs
- scientific article; zbMATH DE number 7228418 (Why is no real title available?)
- List homomorphisms and circular arc graphs
- Bi‐arc graphs and the complexity of list homomorphisms
- scientific article; zbMATH DE number 7651213 (Why is no real title available?)
- Complexity of correspondence \(H\)-colourings
- List-homomorphism problems on graphs and arc consistency
- The parameterised complexity of list problems on graphs of bounded treewidth
- scientific article; zbMATH DE number 1953111 (Why is no real title available?)
- Algebra and the complexity of digraph CSPs: a survey
- Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy
- Vertex ordering with precedence constraints
- A generalization of the theorem of Lekkerkerker and Boland
- Constraint satisfaction problems for reducts of homogeneous graphs
- Multilist layering: Complexity and applications
- Testing list \(H\)-homomorphisms
- The complexity of the list homomorphism problem for graphs
- Parameterized algorithms for min-max multiway cut and list digraph homomorphism
- The complexity of tropical graph homomorphisms
- Complexity of homomorphisms to direct products of graphs
- Descriptive complexity of list H-coloring problems in logspace: a refined dichotomy
- List homomorphisms of graphs with bounded degrees
- List homomorphism: beyond the known boundaries
- Sparsification lower bounds for list \(H\)-coloring
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)
