论文标题
挖掘同态问题和几乎一致多态性的弱
Digraph homomorphism problem and weak near unanimity polymorphism
论文作者
论文摘要
我们认为从输入Digraph $ g $到固定的Digraph $ h $中找到同态的问题。我们表明，如果$ h $承认一个弱接近一致的多态性$ ϕ $，则决定$ g $是否承认$ h $（hom（$ h $））是否可以解决多项式时间。这提供了费德和瓦尔迪的二分法猜想（现为二分法定理）。我们的方法是组合的，它比Bulatov和Zhuk发现的两种算法要简单。我们已经实施了算法并显示了一些实验结果。我们将算法与最近的结果一起使用[38]来识别Maltsev多态性，并在多项式时间内决定是否给定的关系结构$ \ Mathcal {R} $承认弱的一致多态性。
We consider the problem of finding a homomorphism from an input digraph $G$ to a fixed digraph $H$. We show that if $H$ admits a weak near unanimity polymorphism $ϕ$ then deciding whether $G$ admits a homomorphism to $H$ (HOM($H$)) is polynomial-time solvable. This gives proof of the dichotomy conjecture (now dichotomy theorem) by Feder and Vardi. Our approach is combinatorial, and it is simpler than the two algorithms found by Bulatov and Zhuk. We have implemented our algorithm and show some experimental results. We use our algorithm together with the recent result [38] for recognition of Maltsev polymorphisms and decide in polynomial time if a given relational structure $\mathcal{R}$ admits a weak near unanimity polymorphism.
