A Logical Approach to Isomorphism Testing and Constraint Satisfaction

Oleg Verbitsky

  • 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.

Additional References