Graphs, polymorphisms and the complexity of homomorphism problems
Graphs, polymorphisms and the complexity of homomorphism problems
复制标题
图、多态性和同态问题的复杂性
DOI：
10.1145/1374376.1374488
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
T. Niven
中科院分区：
文献类型：
--
作者：
L. Barto;M. Kozik;T. Niven
我们使用多态性和光滑有向图的结构之间的连接来证明Bang-Jensen和Hell从1990年提出的猜想，并由此证明Bang-Jensen，Hell和MacGillivray从1995年提出的猜想。利用泛代数的工具证明了光滑有向图计算复杂染色问题的严格特征。我们引用使用这种新方法获得的进一步的图形结果。证明是基于一个通用的代数框架开发的约束满足问题和CSP二分法猜想的Feder和Vardi特别。
We use a connection between polymorphisms and the structure of smooth digraphs to prove the conjecture of Bang-Jensen and Hell from 1990 and, as a consequence, a conjecture of Bang-Jensen, Hell and MacGillivray from 1995. The conjectured characterization of computationally complex coloring problems for smooth digraphs is proved using tools of universal algebra. We cite further graph results obtained using this new approach. The proofs are based in an universal algebraic framework developed for the Constraint Satisfaction Problem and the CSP dichotomy conjecture of Feder and Vardi in particular.