Computing vertex-surjective homomorphisms to partially reflexive trees

DOI10.1016/j.tcs.2012.06.039zbMath1251.05031OpenAlexW2056827961MaRDI 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 complexitygraph homomorphismsurjectivity

Mathematics Subject Classification ID

Trees (05C05) 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 (8)

Unnamed Item ⋮ Complexity of correspondence \(H\)-colourings ⋮ Finding matching cuts in \(H\)-free graphs ⋮ An algebraic hardness criterion for surjective constraint satisfaction. ⋮ The computational complexity of disconnected cut and \(2 K_2\)-partition ⋮ Surjective \(H\)-colouring: new hardness results ⋮ The Complexity of Counting Surjective Homomorphisms and Compactions ⋮ On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs

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

This page was built for publication: Computing vertex-surjective homomorphisms to partially reflexive trees