×

The complexity of signed graph and edge-coloured graph homomorphisms. (English) Zbl 1351.05099

Summary: We study homomorphism problems of signed graphs from a computational point of view. A signed graph \((G, \Sigma)\) is a graph \(G\) where each edge is given a sign, positive or negative; \(\Sigma \subseteq E(G)\) denotes the set of negative edges. Thus, \((G, \Sigma)\) is a \(2\)-edge-coloured graph with the property that the edge-colours, \(\{+,-\}\), form a group under multiplication. Central to the study of signed graphs is the operation of switching at a vertex, that results in changing the sign of each incident edge. We study two types of homomorphisms of a signed graph \((G, \Sigma)\) to a signed graph \((H, \Pi)\): ec-homomorphisms and s-homomorphisms. Each is a standard graph homomorphism of \(G\) to \(H\) with some additional constraint. In the former, edge-signs are preserved. In the latter, edge-signs are preserved after the switching operation has been applied to a subset of vertices of \(G\).
We prove a dichotomy theorem for \(s\)-homomorphism problems for a large class of (fixed) target signed graphs \((H, \Pi)\). Specifically, as long as \((H, \Pi)\) does not contain a negative (respectively a positive) loop, the problem is polynomial-time solvable if the core of \((H, \Pi)\) has at most two edges, and is NP-complete otherwise. (Note that this covers all simple signed graphs.) The same dichotomy holds if \((H, \Pi)\) has no negative digons, and we conjecture that it holds always. In our proofs, we reduce s-homomorphism problems to certain ec-homomorphism problems, for which we are able to show a dichotomy. In contrast, we prove that a dichotomy theorem for ec-homomorphism problems (even when restricted to bipartite target signed graphs) would settle the dichotomy conjecture of T. Feder and M. Y. Vardi [SIAM J. Comput. 28, No.1, 57–104 (1998; Zbl 0914.68075)].

MSC:

05C22 Signed and weighted graphs
05C15 Coloring of graphs and hypergraphs
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Citations:

Zbl 0914.68075
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alon, N.; Marshall, T. H., Homomorphisms of edge-colored graphs and coxeter groups, J. Algebraic Combin., 8, 1, 5-13 (1998) · Zbl 0911.05034
[2] Brewster, R. C., Vertex colourings of edge-coloured graphs (1993), Simon Fraser University: Simon Fraser University Canada, (Ph.D. thesis)
[3] Brewster, R. C., The complexity of colouring symmetric relational systems, Discrete Appl. Math., 49, 1-3, 95-105 (1994) · Zbl 0810.05025
[4] Brewster, R. C.; Graves, T., Edge-switching homomorphisms of edge-coloured graphs, Discrete Math., 309, 18, 5540-5546 (2009) · Zbl 1213.05066
[5] Brewster, R. C.; Hell, P., On homomorphisms to edge-coloured cycles, Electron. Notes Discrete Math., 5, 46-49 (2009) · Zbl 1412.05064
[6] Feder, T.; Hell, P.; Huang, J., List homomorphisms and circular arc graphs, Combinatorica, 19, 4, 487-505 (1999) · Zbl 0985.05048
[7] Feder, T.; Hell, P.; Huang, J., Bi-arc graphs and the complexity of list homomorphisms, J. Graph Theory, 42, 1, 61-80 (2003) · Zbl 1057.05033
[8] Feder, T.; Vardi, M. Y., The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory, SIAM J. Comput., 28, 1, 57-104 (1998) · Zbl 0914.68075
[10] Galluccio, A.; Hell, P.; Nešetřil, J., The complexity of \(H\)-coloring of bounded degree graphs, Discrete Math., 222, 1-3, 101-109 (2000) · Zbl 0956.05036
[12] Harary, F., On the notion of balance of a signed graph, Michigan Math. J., 2, 2, 143-146 (1953-1954) · Zbl 0056.42103
[13] Hell, P.; Kostochka, A.; Raspaud, A.; Sopena, É., On nice graphs, Discrete Math., 234, 1-3, 39-51 (2001) · Zbl 0990.05058
[14] Hell, P.; Nešetřil, J., On the complexity of \(H\)-coloring, J. Combin. Theory Ser. B, 48, 1, 92-110 (1990) · Zbl 0639.05023
[15] Hell, P.; Nešetřil, J., (Graphs and Homomorphisms. Graphs and Homomorphisms, Oxford Lecture Series in Mathematics and Its Applications (2004), Oxford University Press)
[16] Jensen, T. R.; Toft, B., (Graph Coloring Problems. Graph Coloring Problems, Wiley-Interscience Series in Discrete Mathematics and Optimization (1995))
[17] Klostermeyer, W.; MacGillivray, G., Homomorphisms and oriented colorings of equivalence classes of oriented graphs, Discrete Math., 274, 1-3, 161-172 (2004) · Zbl 1032.05047
[18] König, D., Theorie der endlichen und unendlichen Graphen (1936), Akademische Verlagsgesellschaft: Akademische Verlagsgesellschaft Leipzig · JFM 62.0654.05
[19] MacGillivray, G.; Siggers, M., On the complexity of \(H\)-colouring planar graphs, Discrete Math., 309, 18, 5729-5738 (2009) · Zbl 1213.05094
[22] Montejano, A.; Ochem, P.; Pinlou, A.; Raspaud, A.; Sopena, É., Homomorphisms of \(2\)-edge-colored graphs, Discrete Appl. Math., 158, 12, 1365-1379 (2010) · Zbl 1221.05156
[23] Naserasr, R.; Rollová, E.; Sopena, É., Homomorphisms of planar signed graphs to signed projective cubes, Discrete Math. Theor. Comput. Sci., 15, 3, 1-12 (2013) · Zbl 1283.05186
[24] Naserasr, R.; Rollová, E.; Sopena, É., Homomorphisms of signed graphs, J. Graph Theory, 79, 3, 178-212 (2015) · Zbl 1322.05069
[25] Ochem, P.; Pinlou, A.; Sen, S., Homomorphisms of \(2\)-edge-colored triangle-free planar graphs, J. Graph Theory (2016), in press
[26] Zaslavsky, T., Characterizations of signed graphs, J. Graph Theory, 5, 4, 401-406 (1981) · Zbl 0471.05035
[27] Zaslavsky, T., Signed graphs, Discrete Appl. Math., 4, 1, 47-74 (1982) · Zbl 0476.05080
[28] Zaslavsky, T., Signed graph coloring, Discrete Math., 39, 2, 215-228 (1982) · Zbl 0487.05027
[29] Zaslavsky, T., Chromatic invariants of signed graph, Discrete Math., 42, 2-3, 287-312 (1982) · Zbl 0498.05030
[30] Zaslavsky, T., How colorful the signed graph?, Discrete Math., 52, 2-3, 279-284 (1984) · Zbl 0554.05026
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.