Computing vertex-surjective homomorphisms to partially reflexive trees

DOI10.1016/J.TCS.2012.06.039MaRDI QIDQ714844zbMATH OpenOpenAlexFDO

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

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

Recommendations

• Computing vertex-surjective homomorphisms to partially reflexive trees
• Surjective \(H\)-colouring: new hardness results
• Surjective \(H\)-colouring: new hardness results
• Finding vertex-surjective graph homomorphisms
• Finding vertex-surjective graph homomorphisms

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2044946 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
• A complete complexity classification of the role assignment problem
• Algorithms for partition of some class of graphs under compaction
• Bi‐arc graphs and the complexity of list homomorphisms
• Compaction, Retraction, and Constraint Satisfaction
• Computational Complexity of Compaction to Reflexive Cycles
• Covering graphs with few complete bipartite subgraphs
• Finding vertex-surjective graph homomorphisms
• FindingH-partitions efficiently
• 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
• Graph theory
• Linear time low tree-width partitions and algorithmic consequences
• List homomorphisms to reflexive graphs
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• On the complexity of H-coloring
• Retractions to Pseudoforests
• Strong computational lower bounds via parameterized complexity
• 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 surjective homomorphism problems-a survey
• Which problems have strongly exponential complexity?
• \(2K_2\)-partition of some classes of graphs

Cited in

(15)

• Finding matching cuts in \(H\)-free graphs
• Surjective \texttt{H}-colouring over reflexive digraphs
• The computational complexity of disconnected cut and \(2 K_2\)-partition
• Surjective \(H\)-colouring: new hardness results
• Algebraic global gadgetry for surjective constraint satisfaction
• Finding vertex-surjective graph homomorphisms
• Surjective \(H\)-colouring: new hardness results
• Finding vertex-surjective graph homomorphisms
• Computing vertex-surjective homomorphisms to partially reflexive trees
• The complexity of counting surjective homomorphisms and compactions
• Dichotomies for maximum matching cut: \(H\)-freeness, bounded diameter, bounded radius
• An algebraic hardness criterion for surjective constraint satisfaction.
• Correspondence homomorphisms to reflexive graphs
• Complexity of correspondence \(H\)-colourings
• On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q714844)