We consider homomorphisms of signed graphs from a computational perspective. In particular, we study the list homomorphism problem seeking a homomorphism of an input signed graph $(G,sigma)$, equipped with lists $L(v) subseteq V(H), v in V(G)$, of allowed images, to a fixed target signed graph $(H,pi)$. The complexity of the similar homomorphism problem without lists (corresponding to all lists being $L(v)=V(H)$) has been previously classified by Brewster and Siggers, but the list version remains open and appears difficult. We illustrate this difficulty by classifying the complexity of the problem when $H$ is a tree (with possible loops). The tools we develop will be useful for classifications of other classes of signed graphs, and we illustrate this by classifying the complexity of irreflexive signed graphs in which the unicoloured edges form some simple structures, namely paths or cycles. The structure of the signed graphs in the polynomial cases is interesting, suggesting they may constitute a nice class of signed graphs analogous to the so-called bi-arc graphs (which characterized the polynomial cases of list homomorphisms to unsigned graphs).
تحميل البحث