论文标题
列出签名树的同态问题
List homomorphism problems for signed trees
论文作者
论文摘要
我们从计算角度考虑签名图的同态。特别是，我们研究了列表同构问题，以寻求输入签名的图形$（g，σ）$的同态性，配备了列表$ l（v）\ subseteq v（h），v（g）in允许图像的v \ in v（g）$的v \ in允许的图像，以固定目标签名图$（h，π）$。没有列表的类似同态问题的复杂性（与所有列表相对应$ l（v）= v（h）$）的复杂性先前已由Brewster和Siggers进行了分类，但列表版本仍然打开并且看起来很困难。当$ h $是树（可能的循环）时，我们通过对问题的复杂性进行分类来说明这一困难。我们开发的工具对于其他类签名的图表的分类将很有用，在未来的伴侣论文中，我们将使用它们来对其进行对某些不反复签名的图表进行复杂性进行分类。在多项式情况下，签名树的结构很有趣，这表明问题是多项式的一般签名图可能具有很好的结构，类似于所谓的BI-ARC图（表征了列表同源性的多项式案例以无签名的图表）。
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,σ)$, equipped with lists $L(v) \subseteq V(H), v \in V(G)$, of allowed images, to a fixed target signed graph $(H,π)$. 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 in a future companion paper we will illustrate this by using them to classify the complexity for certain irreflexive signed graphs. The structure of the signed trees in the polynomial cases is interesting, suggesting that the class of general signed graphs for which the problems are polynomial may have nice structure, analogous to the so-called bi-arc graphs (which characterized the polynomial cases of list homomorphisms to unsigned graphs).
