A homomorphism from a graph G to a graph H is a vertex mapping f from the vertex set of G to the vertex set of H such that there is an edge between vertices and of H whenever there is an edge between vertices u and v of G. The H-Colouring problem is to decide if a graph G allows a homomorphism to a fixed graph H. We continue a study on a variant of this problem, namely the SurjectiveH-Colouring problem, which imposes the homomorphism to be vertex-surjective. We build upon previous results and show that this problem is NP-complete for every connected graph H that has exactly two vertices with a self-loop as long as these two vertices are not adjacent. As a result, we can classify the computational complexity of SurjectiveH-Colouring for every graph H on at most four vertices.
M.Bodirsky, J.Kára and B.Martin, The complexity of surjective homomorphism problems – a survey, Discrete Applied Mathematics160 (2012), 1680–1690. doi:10.1016/j.dam.2012.03.029.
2.
A.A.Bulatov, A dichotomy theorem for nonuniform CSPs, in: Proc. FOCS 2017, pp. 319–330.
3.
T.Feder, P.Hell and J.Huang, Bi-arc graphs and the complexity of list homomorphisms, Journal of Graph Theory42 (2003), 61–80. doi:10.1002/jgt.10073.
4.
T.Feder, P.Hell, P.Jonsson, A.Krokhin and G.Nordh, Retractions to pseudoforests, SIAM Journal on Discrete Mathematics24 (2010), 101–112. doi:10.1137/080738866.
5.
T.Feder and M.Y.Vardi, The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory, SIAM Journal on Computing28 (1998), 57–104. doi:10.1137/S0097539794266766.
6.
J.Fiala and J.Kratochvíl, Locally constrained graph homomorphisms – structure, complexity, and applications, Computer Science Review2 (2008), 97–111. doi:10.1016/j.cosrev.2008.06.001.
7.
J.Fiala and D.Paulusma, A complete complexity classification of the role assignment problem, Theoretical Computer Science349 (2005), 67–81. doi:10.1016/j.tcs.2005.09.029.
8.
O.Goldreich, On promise problems (a survey), Lecture Notes in Computer Science3895 (2006), 254–290. doi:10.1007/11685654_12.
P.A.Golovach, D.Paulusma and J.Song, Computing vertex-surjective homomorphisms to partially reflexive trees, Theoretical Computer Science457 (2012), 86–100. doi:10.1016/j.tcs.2012.06.039.
11.
P.Hell and J.Nešetřil, On the complexity of H-colouring, Journal of Combinatorial Theory, Series B48 (1990), 92–110. doi:10.1016/0095-8956(90)90132-J.
12.
P.Hell and J.Nešetřil, Graphs and Homomorphisms, Oxford University Press, 2004.
13.
B.Larose, B.Martin and D.Paulusma, Surjective H-colouring over reflexive digraphs, in: Proc. STACS 2018, 4 Leibniz International Proceedings in Informatics, Vol. 96, 2018, pp. 49:1–49:14.
14.
B.Martin and D.Paulusma, The computational complexity of disconnected cut and -partition, Journal of Combinatorial Theory, Series B111 (2015), 17–37. doi:10.1016/j.jctb.2014.09.002.
15.
M.Patrignani and M.Pizzonia, The complexity of the matching-cut problem, in: Proc. WG 2001, Lecture Notes in Computer Science, Vol. 2204, 2001, pp. 284–295.
16.
N.Vikas, Computational complexity of compaction to reflexive cycles, SIAM Journal on Computing32 (2002), 253–280. doi:10.1137/S0097539701383522.
17.
N.Vikas, Compaction, retraction, and constraint satisfaction, SIAM Journal on Computing33 (2004), 761–782. doi:10.1137/S0097539701397801.
18.
N.Vikas, A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results, Journal of Computer and System Sciences71 (2005), 406–439. doi:10.1016/j.jcss.2004.07.003.
19.
N.Vikas, Algorithms for partition of some class of graphs under compaction and vertex-compaction, Algorithmica67 (2013), 180–206. doi:10.1007/s00453-012-9720-9.
20.
N.Vikas, Computational complexity of graph partition under vertex-compaction to an irreflexive hexagon, in: Proc. MFCS 2017, Leibniz International Proceedings in Informatics, Vol. 83, 2017, pp. 69:1–69:14.
21.
D.Zhuk, A proof of CSP dichotomy conjecture, in: FOCS 2017, pp. 331–342.
