Computing vertex-surjective homomorphisms to partially reflexive trees
A homomorphism from a graph G to a graph H is a vertex mapping f : V-G -> V-H such that f(u) and f(v) form an edge in H whenever u and v form an edge in G. The H-COLORING problem is that of testing whether a graph G allows a homomorphism to a given graph H. A well-known result of Hell and Nesetril determines the computational complexity of this problem for any fixed graph H. We study a natural variant of this problem, namely the SURJECTIVE H-COLORING problem, which is that of testing whether a graph G allows a homomorphism to a graph H that is (vertex-)surjective. We classify the computational complexity of this problem for when H is any fixed partially reflexive tree. Thus we identify the first class of target graphs H for which the computational complexity of SURJECTIVE H-COLORING can be determined. For the polynomial-time solvable cases we show a number of parameterized complexity results, including in particular ones on graph classes with (locally) bounded expansion. (C) 2012 Elsevier B.V. All rights reserved.
surjectivity computational complexity graph homomorphism