论文标题
Digraphs同态问题与MALTSEV状况
Digraphs Homomorphism Problems with Maltsev Condition
论文作者
论文摘要
我们考虑从输入Digraph $ g $到固定的Digraph $ h $，HOM（$ H $）发现同构的概括。在这种情况下，我们将获得一个输入Digraph $ g $，并将列表功能从$ g $到$ 2^h $。目的是在一个存在的情况下找到从$ g $到$ h $的同态性。 我们表明，如果列表功能是麦芽式多态性的，那么决定$ g $是否承认同构为$ h $是多项式时间。在我们的方法中，我们仅利用麦芽菌多态性的存在。此外，我们表明，确定关系结构$ \ MATHCAL {R} $承认Maltsev多态性是一种特殊情况，是从图$ g $中找到图形$ h $的施加型，并具有MALTSEV多晶型的列表功能。由于我们的算法中不需要Maltsev的存在，因此我们可以在多项式时间内确定关系结构$ \ MATHCAL {R} $是否允许Maltsev。 我们还讨论了承认Maltsev列表多态性的情况的禁止障碍。我们已经实施了算法，并在线性方程和其他类型的实例中对实例进行了测试。
We consider a generalization of finding a homomorphism from an input digraph $G$ to a fixed digraph $H$, HOM($H$). In this setting, we are given an input digraph $G$ together with a list function from $G$ to $2^H$. The goal is to find a homomorphism from $G$ to $H$ with respect to the lists if one exists. We show that if the list function is a Maltsev polymorphism then deciding whether $G$ admits a homomorphism to $H$ is polynomial time solvable. In our approach, we only use the existence of the Maltsev polymorphism. Furthermore, we show that deciding whether a relational structure $\mathcal{R}$ admits a Maltsev polymorphism is a special case of finding a homormphism from a graph $G$ to a graph $H$ and a list function with a Maltsev polymorphism. Since the existence of Maltsev is not required in our algorithm, we can decide in polynomial time whether the relational structure $\mathcal{R}$ admits Maltsev or not. We also discuss forbidden obstructions for the instances admitting Maltsev list polymorphism. We have implemented our algorithm and tested on instances arising from linear equations, and other types of instances.
