The complexity of surjective homomorphism problems-a survey

DOI10.1016/j.dam.2012.03.029zbMath1246.05104MaRDI 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 complexity; constraint satisfaction; surjective homomorphisms

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Related Items

Unnamed Item, Constraint Satisfaction with Counting Quantifiers, The Complexity of Counting Surjective Homomorphisms and Compactions, Algorithms and almost tight results for 3-colorability of small diameter graphs, An algebraic hardness criterion for surjective constraint satisfaction., Tractability conditions for numeric CSPs, Computing vertex-surjective homomorphisms to partially reflexive trees, Finding vertex-surjective graph homomorphisms, Obtaining online ecological colourings by generalizing first-fit, Independent feedback vertex sets for graphs of bounded diameter, Surjective \(H\)-colouring: new hardness results, Graph partitions with prescribed patterns

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