Oleg Verbitsky ; Maksim Zhukovskii - On the First-Order Complexity of Induced Subgraph Isomorphism

lmcs:4299 - Logical Methods in Computer Science, March 6, 2019, Volume 15, Issue 1 - https://doi.org/10.23638/LMCS-15(1:25)2019
On the First-Order Complexity of Induced Subgraph IsomorphismArticle

Authors: Oleg Verbitsky ; Maksim Zhukovskii

    Given a graph $F$, let $I(F)$ be the class of graphs containing $F$ as an induced subgraph. Let $W[F]$ denote the minimum $k$ such that $I(F)$ is definable in $k$-variable first-order logic. The recognition problem of $I(F)$, known as Induced Subgraph Isomorphism (for the pattern graph $F$), is solvable in time $O(n^{W[F]})$. Motivated by this fact, we are interested in determining or estimating the value of $W[F]$. Using Olariu's characterization of paw-free graphs, we show that $I(K_3+e)$ is definable by a first-order sentence of quantifier depth 3, where $K_3+e$ denotes the paw graph. This provides an example of a graph $F$ with $W[F]$ strictly less than the number of vertices in $F$. On the other hand, we prove that $W[F]=4$ for all $F$ on 4 vertices except the paw graph and its complement. If $F$ is a graph on $t$ vertices, we prove a general lower bound $W[F]>(1/2-o(1))t$, where the function in the little-o notation approaches 0 as $t$ inreases. This bound holds true even for a related parameter $W^*[F]\le W[F]$, which is defined as the minimum $k$ such that $I(F)$ is definable in the infinitary logic $L^k_{\infty\omega}$. We show that $W^*[F]$ can be strictly less than $W[F]$. Specifically, $W^*[P_4]=3$ for $P_4$ being the path graph on 4 vertices. Using the lower bound for $W[F]$, we also obtain a succintness result for existential monadic second-order logic: A usage of just one monadic quantifier sometimes reduces the first-order quantifier depth at a super-recursive rate.

    Volume: Volume 15, Issue 1
    Published on: March 6, 2019
    Accepted on: October 16, 2018
    Submitted on: February 20, 2018
    Keywords: Computer Science - Computational Complexity,Computer Science - Logic in Computer Science,F.4.1

    2 Documents citing this article

    Consultation statistics

    This page has been seen 1267 times.
    This article's PDF has been downloaded 245 times.