Computing vertex-surjective homomorphisms to partially reflexive trees
From MaRDI portal
Publication:714844
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
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, Finding matching cuts in \(H\)-free graphs, An algebraic hardness criterion for surjective constraint satisfaction., Surjective \(H\)-colouring: new hardness results, On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs, Complexity of correspondence \(H\)-colourings, The computational complexity of disconnected cut and \(2 K_2\)-partition, Unnamed Item
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