Oleg Verbitsky

• Area: LoCo
• Level: A
• Week: 1
• Time: 14:00 – 15:30
• Room: C2.06

Abstract

We will study the relationship between the definability of graphs in first-order logic and the computational complexity of the graph isomorphism and homomorphism problems. If every graph in a class of graphs $C$ is definable with $k$ variables, then the isomorphism problem for $C$ is solvable in polynomial time by the $(k-1)$-dimensional Weisfeiler-Leman algorithm. Moreover, definability with finitely many variables and logarithmic quantifier depth implies that isomorphism can be tested even in parallel logarithmic time. The existential-positive fragment of $k$-variable logic corresponds to the algorithmic techniques for homomorphism testing (i.e., constraint satisfaction) known as $k$-Consistency Checking. Examining the expressibility of this logic, we are able to estimate the time efficiency of this approach to constraint satisfaction.

Slides

Part 1. Logical complexity of graphs: Basic definitions and examples.
Part 2. Isomorphism testing by Color Refinement and two-variable counting logic.
Part 3. The graphs definable with two variables and counting quantifiers.
Part 4. Two-variable counting logic and linear-programming methods.
Part 5. Two-variable counting logic and distributed computing.
Part 6. Existential-positive two-variable logic and Constraint Satisfaction.
Part 7. Alternation hierarchy of two-variable logic.
Part 8. Counting logic with 3 and more variables: Applications to isomorphism testing.

Additional References

• O.Pikhurko and O.Verbitsky. Logical complexity of graphs: a survey. In: Model Theoretic Methods in Finite Combinatorics. Contemporary Mathematics, Vol. 558, pages 129-179. American Mathematical Society (2011).
• V.Arvind, J.Köbler, G.Rattan and O.Verbitsky. Graph Isomorphism, Color Refinement, and Compactness. A combined version of conference papers in FCT’15 and MFCS’15.
• A.Krebs and O.Verbitsky. Universal covers, color refinement, and two-variable logic with counting quantifiers: Lower bounds for the depth.
  Proc. LICS’15, pp. 689-700 (2015).
• C.Berkholz and O.Verbitsky. On the speed of constraint propagation and the time complexity of arc consistency testing. Proc. MFCS’13, Vol. 8087 of LNCS, pp. 159-170 (2013).
• C.Berkholz, A.Krebs, and O.Verbitsky. Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy. ACM Transactions on Computational Logic 16, Article 21 (2015).
• M.Grohe and O.Verbitsky. Testing graph isomorphism in parallel by playing a game. Proc. ICALP’06, Vol. 4051 of LNCS, pp. 3-14 (2006).