- Area: LoCo
- Level: A
- Week: 1
- Time: 14:00 – 15:30
- Room: C2.06
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.
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.
- 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).