Finding vertex-surjective graph homomorphisms
Petr A. Golovach, Barnaby D. Martin, Daniël Paulusma, et al. · 2012
Abstract. The Surjective Homomorphism problem is to test whether a given graph G called the guest graph allows a vertex-surjective ho-momorphism to some other given graph H called the host graph. The bijective and injective homomorphism problems can be formulated in terms of spanning subgraphs and subgraphs, and as such their computa-tional complexity has been extensively studied. What about the surjec-tive variant? Because this problem is NP-complete in general, we restrict the guest and the host graph to belong to graph classes G and H, re-spectively. We determine to what extent a certain choice of G and H influences its computational complexity. We observe that the problem is polynomial-time solvable if H is the class of paths, whereas it is NP-complete if G is the class of paths. Moreover, we show that the problem is even NP-complete on many other elementary graph classes, namely lin-ear forests, unions of complete graphs, cographs, proper interval graphs, split graphs and trees of pathwidth at most 2. In contrast, we prove that the problem is fixed-parameter tractable in k if G is the class of trees and H is the class of trees with at most k leaves, or if G and H are equal to the class of graphs with vertex cover number at most k. 1