Frontiers of Tractability for Graph Isomorphism and Homomorphism Problems

• Applicant: Dr. Oleg Verbitsky
• Subject Area: Theoretical Computer Science
• Term: from 2011 to 2016
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 197227691

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.

• DFG Programme: Research Grants