论文标题
Deep Weisfeiler Leman
Deep Weisfeiler Leman
论文作者
论文摘要
我们介绍了Deep Weisfeiler Leman算法（DEEPWL）的框架，该算法允许设计纯粹的组合图同构测试，这些同构测试比知名的Weisfeiler-Leman算法更强大。 我们证明，作为一个抽象的计算模型，多项式时间深wl-Algorithm具有与Blass，Gurevich和Shelah引入的逻辑无序多项式时间完全相同的表达性（Ann。PureAppl。Logic。，1999）。 这是一个众所周知的开放问题，是否存在多项式时间图同构测试是否意味着多项式时间典礼算法的存在。我们的主要技术结果指出，对于每类图（满足某些轻度闭合条件），如果有多项式时间深WL同构测试，则该类别的多项式典型化算法。这意味着此类还存在逻辑捕获多项式时间。
We introduce the framework of Deep Weisfeiler Leman algorithms (DeepWL), which allows the design of purely combinatorial graph isomorphism tests that are more powerful than the well-known Weisfeiler-Leman algorithm. We prove that, as an abstract computational model, polynomial time DeepWL-algorithms have exactly the same expressiveness as the logic Choiceless Polynomial Time (with counting) introduced by Blass, Gurevich, and Shelah (Ann. Pure Appl. Logic., 1999) It is a well-known open question whether the existence of a polynomial time graph isomorphism test implies the existence of a polynomial time canonisation algorithm. Our main technical result states that for each class of graphs (satisfying some mild closure condition), if there is a polynomial time DeepWL isomorphism test then there is a polynomial canonisation algorithm for this class. This implies that there is also a logic capturing polynomial time on this class.
