TREE-DEPTH AND THE FORMULA COMPLEXITY OF SUBGRAPH ISOMORPHISM

For a fixed "pattern" graph G, the colored G-subgraph isomorphism problem (denoted by 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 bytd (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((Omega) over tilde (td( G)1/3)) lower bound for formulas that are monotone or have sublogarithmic depth. This complements a lower bound of Li, Razborov, and Rossman [SIAM J. Comput., 46 (2017), pp. 936-971] 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 [B. Rossman, An improved homomorphism preservation theorem from lower bounds in circuit complexity, in 8th Innovations in Theoretical Computer Science Conference, LIPIcs. Leibniz Int. Proc. Inform. 67, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2017, 27]. 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 B. Rossman [SIAM J. Comput., 47 (2018), pp. 1986-2028]. (The lower bound for general patterns follows via a recent excluded-minor characterization of tree-depth [W. Czerwi\'nski, W. Nadara, and M. Pilipczuk, SIAM J. Discrete Math., 35 (2021), pp. 934-947; K. Kawarabayashi and B. Rossman, A polynomial excluded-minor approximation of treedepth, in Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms, 2018, pp. 234-246]. 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.