Math @ Duke

Publications [#355193] of Benjamin Rossman
Papers Published
 Kush, D; Rossman, B, Treedepth and the formula complexity of subgraph isomorphism,
Annual Symposium on Foundations of Computer Science (Proceedings), vol. 2020November
(November, 2020),
pp. 3142, ISBN 9781728196213 [doi]
(last updated on 2022/01/23)
Abstract: For a fixed'pattern' graph G, the colored Gsubgraph isomorphism problem (denoted text{SUB}(G)) asks, given an nvertex 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 treedepth (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 sublogarithmic depth. This complements a lower bound of Li, Razborov and Rossman [8] relating treewidth and AC circuit size. As a corollary, it implies a stronger homomorphism preservation theorem for firstorder 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 excludedminor characterization of treedepth [4], [6].) Additional results of this paper extend the pathset framework and improve upon both, the best known upper and lower bounds on the averagecase formula size of text{SUB}(G) when G is a path.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

