Golovach, Petr A.; Lidický, Bernard; Martin, Barnaby; Paulusma, Daniël Finding vertex-surjective graph homomorphisms. (English) Zbl 1253.68149 Acta Inf. 49, No. 6, 381-394 (2012). Summary: The Surjective Homomorphism problem is to test whether a given graph \(G\) called the guest graph allows a vertex-surjective homomorphism 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 computational complexity has been extensively studied. What about the surjective variant? Because this problem is NP-complete in general, we restrict the guest and the host graph to belong to graph classes \({{\mathcal G}}\) and \({{\mathcal H}}\), respectively. We determine to what extent a certain choice of \({{\mathcal G}}\) and \({{\mathcal H}}\) influences its computational complexity. We observe that the problem is polynomial-time solvable if \({{\mathcal H}}\) is the class of paths, whereas it is NP-complete if \({{\mathcal G}}\) is the class of paths. Moreover, we show that the problem is even NP-complete on many other elementary graph classes, namely linear 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 \({{\mathcal G}}\) is the class of trees and \({{\mathcal H}}\) is the class of trees with at most \(k\) leaves, or if \({{\mathcal G}}\) and \({{\mathcal H}}\) are equal to the class of graphs with vertex cover number at most \(k\). Cited in 4 Documents MSC: 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.) Keywords:surjective homomorphism problem; guest graph; host graph; NP-complete PDFBibTeX XMLCite \textit{P. A. Golovach} et al., Acta Inf. 49, No. 6, 381--394 (2012; Zbl 1253.68149) Full Text: DOI Link References: [1] Adiga, A., Chitnis, R., Saurabh, S.: Parameterized algorithms for boxicity. In: Proceedings of ISAAC 2010, LNCS 6506, pp. 366–377 (2010) · Zbl 1310.68154 [2] Bodirsky M., Kára J., Martin B.: The complexity of surjective homomorphism problems–a survey. Discrete Appl. Math. 160, 1680–1690 (2012) · Zbl 1246.05104 [3] Chen, J., Kanj, I.A., Xia, G.: Improved parameterized upper bounds for vertex cover. In: Proceedings of MFCS 2006, LNCS 4162, pp. 238–249 (2006) · Zbl 1132.68421 [4] Courcelle B., Olariu S.: Upper bounds to the clique width of graphs. Discrete Appl. Math. 101, 77–114 (2000) · Zbl 0958.05105 [5] Dalmau, V., Kolaitis, P.G., Vardi, M.Y.: Constraint satisfaction, bounded treewidth, and finite-variable logics. In: Proceedings of CP 2002, LNCS 2470, pp. 223–254 (2006) [6] Enciso, R., Fellows, M.R., Guo, J., Kanj, I.A., Rosamond, F.A., Suchý, O.: What makes equitable connected partition easy, In: Proceedings of IWPEC 2009, LNCS 5917, pp. 122–133 (2009) · Zbl 1273.68164 [7] Feder T., Hell P., Jonsson P., Krokhin A., Nordh G.: Retractions to pseudoforests. SIAM J. Discrete Math. 24, 101–112 (2010) · Zbl 1215.05063 [8] Fellows, M.R., Lokshtanov, D., Misra, N., Rosamond, F.A., Saurabh, S.: Graph layout problems parameterized by vertex cover. In: Proceedings of ISAAC 2008, LNCS 5369, pp. 294–305 (2008) · Zbl 1183.68424 [9] Fiala J., Kratochvíl J.: Locally constrained graph homomorphisms–structure, complexity, and applications. Comput. Sci. Rev. 2, 97–111 (2008) · Zbl 1302.05122 [10] Fiala J., Golovach P.A., Kratochvíl J.: Parameterized complexity of coloring problems: treewidth versus vertex cover. Theor. Comput. Sci. 412, 2513–2523 (2011) · Zbl 1216.68127 [11] Fiala J., Paulusma D.: A complete complexity classification of the role assignment problem. Theor. Comput. Sci. 349, 67–81 (2005) · Zbl 1124.91055 [12] Flum J., Grohe M.: Parameterized Complexity Theory, Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2006) [13] Frank A., Tardos É.: An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica 7, 49–65 (1987) · Zbl 0641.90067 [14] Garey M.R., Johnson D.R.: Computers and Intractability. Freeman, New York (1979) · Zbl 0411.68039 [15] Golovach, P.A., Paulusma, D., Song, J.: Computing vertex-surjective homomorphisms to partially reflexive trees. Proceedings of CSR 2011, LNCS 6651, pp. 261–274 (2011) · Zbl 1332.68073 [16] Grohe, M.: The complexity of homomorphism and constraint satisfaction problems seen from the other side. J ACM 54(1), Art no 1 (2007) · Zbl 1312.68101 [17] Hell P., Nešetřil J.: On the complexity of H-colouring. J. Comb. Theory Ser. B 48, 92–110 (1990) · Zbl 0639.05023 [18] Hell P., Nešetřil J.: Graphs and Homomorphisms. Oxford University Press, Oxford (2004) [19] Lenstra H.W. Jr.: Integer programming with a fixed number of variables. Math. Oper. Res. 8, 538–548 (1983) · Zbl 0524.90067 [20] Martin, B., Paulusma, D.: The computational complexity of disconnected cut and 2K2-Partition. In: Proceedings of CP 2011, LNCS 6876, pp. 561–575 (2011) [21] Vikas N.: Computational complexity of compaction to reflexive cycles. SIAM J. Comput. 32, 253–280 (2002) · Zbl 1029.68085 [22] Vikas N.: Compaction, retraction, and constraint satisfaction. SIAM J. Comput. 33, 761–782 (2004) · Zbl 1101.68612 [23] Vikas N.: A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results. J. Comput. Syst. Sci. 71, 406–439 (2005) · Zbl 1101.68613 [24] Vikas, N.: Algorithms for partition of some class of graphs under compaction. In: Proceedings of COCOON 2011, LNCS 6842, pp. 319–330 (2011) · Zbl 1353.05119 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.