The complexity of signed graph and edge-coloured graph homomorphisms

Abstract

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 Feder and Vardi.

21 pages; 6 figures. In this version, we have adopted some changes in terminology and notation

Cited by in corpus (13)

• Concepts of signed graph coloring
• The complexity of tropical graph homomorphisms
• Complexity of planar signed graph homomorphisms to cycles
• List homomorphism problems for signed trees
• Graph Homomorphism Reconfiguration and Frozen $H$-Colourings
• Homomorphism bounds of signed bipartite $K_4$-minor-free graphs and edge-colorings of $2k$-regular $K_4$-minor-free multigraphs
• Nowhere-zero flows in signed graphs: A survey
• The 2-colouring problem for $(m,n)$-mixed graphs with switching is polynomial
• Switching $(m,n)$-mixed graphs with respect to Abelian groups
• List homomorphisms to separable signed graphs
• Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity
• Extended Double Covers and Homomorphism Bounds of Signed Graphs
• Coloring problem of signed interval graphs