Paper Info
Title
ON THE FIRST-ORDER COMPLEXITY OF INDUCED SUBGRAPH ISOMORPHISM
Abstract
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.
Year
DOI
Venue
2017
10.23638/LMCS-15(1:25)2019
LOGICAL METHODS IN COMPUTER SCIENCE
Keywords
DocType
Volume
The induced subgraph isomorphism problem,descriptive and computational complexity,finite-variable first-order logic,quantifier depth and variable width
Conference
15
Issue
ISSN
Citations 
1
1860-5974
1
PageRank 
References 
Authors
0.41
12
2
Name
Order
Citations
PageRank
Oleg Verbitsky119127.50
Maksim Zhukovskii224.51