Frontiers of Tractability for Graph Isomorphism and Homomorphism Problems

我们的总体目标是图上同构和同态(即约束满足)问题的当前可处理边界的扩展。虽然一般来说，这两类问题在复杂性层次中占据不同的层次，但我们专注于从共同的角度处理它们的方法。这些方法基于有限变量一阶逻辑中输入图的可定义性及其存在的正碎片.具有对数量词深度的k变量逻辑中的图的可定义性意味着这类图的同构在NC中是可由k维Weisfeler-Lehman算法的自然并行化版本来判定的.即使用计数量词来扩展语法，这也是成立的.有时NC结果可以进一步改进为一种对数空间算法，它不明确地依赖于原始的描述复杂性分析.利用这一方法，我们打算得到几类重要图的新的可达性结果。K-变量存在正逻辑的可表现性对应于约束满足研究中称为k-一致性检查的同态测试的算法技术。在这里，我们期望对描述复杂性的彻底分析将使我们得到新的算法结果，并建立k-一致性检查效率的下界。k=2，3的情况对应于圆弧和路径一致性，这是解决有界宽度的约束满足问题的主要工具。对于有界宽度的约束满足问题，我们研究了参数k的最优值作为输入大小的函数，并将一致性检验放在精确指数算法的研究范围内，我们还计划研究局部双射同态(或覆盖映射)在各种局部和分布式计算模型中的应用。

Our overall objective is an extension of the current frontiers oftractability for isomorphism and homomorphism (i.e., constraint satisfaction)problems on graphs. Though in general the two classes of problems occupydifferent levels of the complexity hierarchy, we focus on methodsallowing to treat them from a common perspective. These methods are basedon definability of input graphs in a finite-variable first-orderlogic and its existential-positive fragment.The definability of graphs in k-variable logic with logarithmic quantifier depth impliesthat isomorphism of such graphs is decidable in NC by a naturalparallelized version of the k-dimensional Weisfeiler-Lehman algorithm.This holds true even if the syntax is extended with counting quantifiers.Sometimes the NC result can further be improved to a logspace algorithm,that does not rely explicitly on the original descriptive complexityanalysis. Using this approach, we intend to obtain new tractabilityresults for several important classes of graphs. The expressibility in k-variable existential-positive logic corresponds to the algorithmic techniques for homomorphism testing known in the constraint satisfaction research as k-Consistency Checking.Here we expect that a thorough analysis of descriptive complexitywill allow us to obtain new algorithmic results as well asto establish lower bounds for the efficiency of k-Consistency Checking.The cases of k=2,3 correspond to Arc and Path Consistency, which areprincipal tools for solving constraint satisfaction problems ofbounded width. For constraint satisfaction problems ofunbounded width we study the optimum value of the parameter kas a function of the input size and put consistency checkingin the context of research on exact exponential algorithms.We also plan to investigate locally bijective homomorphisms(or covering maps) in the context of their applications tovarious models of local and distributed computations.