Tree-depth and the Formula Complexity of Subgraph Isomorphism

For a fixed "pattern" graph G, the colored G-subgraph isomorphism problem (denoted SUB(G)) asks, given an n-vertex graph H and a coloring V (H) → 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 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 SUB(G) and an invariant known as tree-depth (denoted td(G)). SUB(G) is known to be solvable by monotone AC 0 formulas of size O(n td(G) ). Our main result is an n Ω(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 0 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 Ω(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 SUB(G) when G is a path.