ON THE FIRST-ORDER COMPLEXITY OF INDUCED SUBGRAPH ISOMORPHISM

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 l vertices, we prove a general lower bound W[F] > (1/2 - o(1))l, where the function in the little-o notation approaches 0 as l increases. This bound holds true even for a related parameter W* [F] <= W[F], which is defined as the minimum k such that I(F) is definable in the infinitary logic L-infinity omega(k). 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 single monadic quantifier sometimes reduces the first-order quantifier depth at a super-recursive rate.