Oleg Verbitsky
- Area: LoCo
- Level: A
- Week: 1
- Room:
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.