Tree-depth and the formula complexity of subgraph isomorphism
For a fixed'pattern' graph G, the colored G-subgraph isomorphism problem (denoted text{SUB}(G)) asks, given an n-vertex graph H and a coloring V(H) rightarrow V(G), whether H contains a properly colored copy of G. The complexity of this problem is tied to parameterized versions of P=? NP and L=? NL, among other questions. An overarching goal is to understand the complexity of text{SUB}(G), under different computational models, in terms of natural invariants of the pattern graph G. In this paper, we establish a close relationship between the formula complexity of text{SUB}(G) and an invariant known as tree-depth (denoted td (G)). text{SUB}(G) is known to be solvable by monotone AC{0} formulas of size O(n{text{td}(G)}). Our main result is an n{widetilde{Omega}(text{td}(G){1/3})} lower bound for formulas that are monotone or have sub-logarithmic depth. This complements a lower bound of Li, Razborov and Rossman [8] relating tree-width and AC circuit size. As a corollary, it implies a stronger homomorphism preservation theorem for first-order logic on finite structures [14]. The technical core of this result is an n{Omega(k)} lower bound in the special case where G is a complete binary tree of height k, which we establish using the pathset framework introduced in [15]. (The lower bound for general patterns follows via a recent excluded-minor characterization of tree-depth [4], [6].) Additional results of this paper extend the pathset framework and improve upon both, the best known upper and lower bounds on the average-case formula size of text{SUB}(G) when G is a path.
