Computing vertex-surjective homomorphisms to partially reflexive trees

DOI10.1016/j.tcs.2012.06.039zbMath1251.05031MaRDI QIDQ714844

Jian Song, Petr A. Golovach, Daniël Paulusma

Publication date: 11 October 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.06.039

zbMATH Keywords

computational complexity; graph homomorphism; surjectivity

Mathematics Subject Classification ID

05C05: Trees

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

The Complexity of Counting Surjective Homomorphisms and Compactions, An algebraic hardness criterion for surjective constraint satisfaction., Surjective \(H\)-colouring: new hardness results, The computational complexity of disconnected cut and \(2 K_2\)-partition

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of surjective homomorphism problems-a survey
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• A complete complexity classification of the role assignment problem
• Strong computational lower bounds via parameterized complexity
• Covering graphs with few complete bipartite subgraphs
• On the complexity of H-coloring
• List homomorphisms to reflexive graphs
• Which problems have strongly exponential complexity?
• \(2K_2\)-partition of some classes of graphs
• Grad and classes with bounded expansion. I: Decompositions
• Grad and classes with bounded expansion. II: Algorithmic aspects
• Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities
• A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
• Finding Vertex-Surjective Graph Homomorphisms
• Linear time low tree-width partitions and algorithmic consequences
• Retractions to Pseudoforests
• Algorithms for Partition of Some Class of Graphs under Compaction
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Compaction, Retraction, and Constraint Satisfaction
• FindingH-partitions efficiently
• Computational Complexity of Compaction to Reflexive Cycles
• Bi‐arc graphs and the complexity of list homomorphisms
• The complexity of satisfiability problems