Frontiers of Tractability for Graph Isomorphism and Homomorphism Problems

Our overall objective is an extension of the current frontiers of tractability for isomorphism and homomorphism (i.e., constraint satisfaction) problems on graphs. Though in general the two classes of problems occupy different levels of the complexity hierarchy, we focus on methods allowing to treat them from a common perspective. These methods are based on definability of input graphs in a finite-variable first-order logic and its existential-positive fragment. The definability of graphs in k-variable logic with logarithmic quantifier depth implies that isomorphism of such graphs is decidable in NC by a natural parallelized 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 complexity analysis. Using this approach, we intend to obtain new tractability results 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 complexity will allow us to obtain new algorithmic results as well as to establish lower bounds for the efficiency of k-Consistency Checking. The cases of k=2,3 correspond to Arc and Path Consistency, which are principal tools for solving constraint satisfaction problems of bounded width. For constraint satisfaction problems of unbounded width we study the optimum value of the parameter k as a function of the input size and put consistency checking in 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 to various models of local and distributed computations.

Duration of Project

Start date: 02/2015

End date: 01/2016