权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Frontiers of Tractability for Graph Isomorphism and Homomorphism Problems

图同构和同态问题的可处理性前沿

基本信息

批准号：
197227691
负责人：
Dr. Oleg Verbitsky
金额：
--
依托单位：
Institut für Informatik
依托单位国家：
德国
项目类别：
Research Grants
财政年份：
2011
资助国家：
德国
起止时间：
2010-12-31 至 2015-12-31
项目状态：
已结题

来源：
https://gepris.dfg.de/gepris/projekt/197227691?language=en
关键词：
Frontiers Tractability Graph Isomorphism Homomorphism

项目摘要

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.

我们的总体目标是扩展同构和同态的当前前沿易处理性（即，约束满足）问题。虽然在一般情况下，这两类问题占据不同层次的复杂性层次结构，我们专注于方法，从一个共同的角度来对待他们。这些方法是基于有限变量一阶逻辑中输入图的可定义性及其存在正片段.具有对数量词深度的k-变量逻辑中图的可定义性意味着这类图的同构在NC中可由k维Weisfeiler的自然并行版本判定. Lehman算法。即使语法扩展了计数量词，也是如此。有时NC结果可以进一步改进为对数空间算法，这并不依赖于原始的描述性复杂性分析。使用这种方法，我们打算获得新的tractability结果的几个重要类的图。k-变量存在正逻辑中的可表达性对应于约束满足研究中的同态检验算法技术，即k-一致性检验。本文期望通过对描述复杂性的深入分析，获得新的算法结果，并建立k-一致性检验效率的下界。k= 2，3的情况对应于弧和路径一致性，是求解有界宽度约束满足问题的主要工具。对于无界宽度的约束满足问题，我们研究了参数kas作为输入大小的函数的最优值，并在精确指数算法的研究中进行了一致性检验，我们还计划研究局部双射同态（或覆盖映射）在各种局部和分布式计算模型中的应用.