The complexity of surjective homomorphism problems-a survey

DOI10.1016/j.dam.2012.03.029zbMath1246.05104OpenAlexW1998601876MaRDI QIDQ444433

Jan Kára, Barnaby Martin, Manuel Bodirsky

Publication date: 14 August 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2012.03.029

zbMATH Keywords

computational complexityconstraint satisfactionsurjective homomorphisms

Mathematics Subject Classification ID

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 (33)

Coloring problems on bipartite graphs of small diameter ⋮ Unnamed Item ⋮ Partitioning \(H\)-free graphs of bounded diameter ⋮ Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter ⋮ Unnamed Item ⋮ Obtaining online ecological colourings by generalizing first-fit ⋮ Independent feedback vertex sets for graphs of bounded diameter ⋮ Disconnected cuts in claw-free graphs ⋮ Complexity of \(C_k\)-coloring in hereditary classes of graphs ⋮ Constraint satisfaction problem: what makes the problem easy ⋮ 3-coloring \(C_4\) or \(C_3\)-free diameter two graphs ⋮ A note on rainbow-free colorings of uniform hypergraphs ⋮ Unnamed Item ⋮ Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs ⋮ Minimum Violation Vertex Maps and Their Applications to Cut Problems ⋮ An algebraic hardness criterion for surjective constraint satisfaction. ⋮ The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems ⋮ On rainbow-free colourings of uniform hypergraphs ⋮ Tractability conditions for numeric CSPs ⋮ Unnamed Item ⋮ Surjective \(H\)-colouring: new hardness results ⋮ Computing vertex-surjective homomorphisms to partially reflexive trees ⋮ Finding vertex-surjective graph homomorphisms ⋮ Constraint Satisfaction with Counting Quantifiers ⋮ Unnamed Item ⋮ Graph partitions with prescribed patterns ⋮ Colouring graphs of bounded diameter in the absence of small cycles ⋮ Acyclic, star, and injective colouring: bounding the diameter ⋮ Colouring graphs of bounded diameter in the absence of small cycles ⋮ Acyclic, star, and injective colouring: bounding the diameter ⋮ The Complexity of Counting Surjective Homomorphisms and Compactions ⋮ Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations ⋮ Algorithms and almost tight results for 3-colorability of small diameter graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The external constraint 4 nonempty part sandwich problem
• Computational complexity of compaction to irreflexive cycles
• Computing role assignments of chordal graphs
• A complete complexity classification of the role assignment problem
• \(2K_{2}\) vertex-set partition into nonempty parts
• Covering graphs with few complete bipartite subgraphs
• List homomorphisms to reflexive graphs
• On the algebraic structure of combinatorial problems
• List homomorphisms and circular arc graphs
• On disconnected cuts and separators
• Tractable cases of the extended global cardinality constraint
• Coloring mixed hypertrees
• A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Finding Vertex-Surjective Graph Homomorphisms
• Complexity of conservative constraint satisfaction problems
• Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees
• The complexity of global cardinality constraints
• Retractions to Pseudoforests
• Algorithms for Partition of Some Class of Graphs under Compaction
• The Complexity of Rooted Phylogeny Problems
• The Complexity of the List Partition Problem for Graphs
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Undirected connectivity in log-space
• Parameterizing Cut Sets in a Graph by the Number of Their Components
• The Complexity of Colouring by Semicomplete Digraphs
• On the Structure of Polynomial Time Reducibility
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• On generating all solutions of generalized satisfiability problems
• List Partitions
• Compaction, Retraction, and Constraint Satisfaction
• FindingH-partitions efficiently
• Computational Complexity of Compaction to Reflexive Cycles
• Bi‐arc graphs and the complexity of list homomorphisms
• Classifying the Complexity of Constraints Using Finite Algebras
• The complexity of satisfiability problems
• The Approximability of Three-valued MAX CSP

This page was built for publication: The complexity of surjective homomorphism problems-a survey