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 by (G)). SUB(G) is known to be solvable by monotone AC0 formulas of size O(n (G)). Our main result is an n Ω ((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 AC0 circuit size. As a corollary, it implies a stronger homomorphism preservation theorem for firstorder 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Ω (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ński, 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 ACMSIAM 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.

Duke Scholars

Author Benjamin Rossman Computer Science