Skip to main content

Tree-depth and the formula complexity of subgraph isomorphism

Publication ,  Conference
Kush, D; Rossman, B
Published in: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
November 1, 2020

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.

Duke Scholars

Published In

Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

DOI

ISSN

0272-5428

ISBN

9781728196213

Publication Date

November 1, 2020

Volume

2020-November

Start / End Page

31 / 42
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Kush, D., & Rossman, B. (2020). Tree-depth and the formula complexity of subgraph isomorphism. In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS (Vol. 2020-November, pp. 31–42). https://doi.org/10.1109/FOCS46700.2020.00012
Kush, D., and B. Rossman. “Tree-depth and the formula complexity of subgraph isomorphism.” In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2020-November:31–42, 2020. https://doi.org/10.1109/FOCS46700.2020.00012.
Kush D, Rossman B. Tree-depth and the formula complexity of subgraph isomorphism. In: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. 2020. p. 31–42.
Kush, D., and B. Rossman. “Tree-depth and the formula complexity of subgraph isomorphism.” Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, vol. 2020-November, 2020, pp. 31–42. Scopus, doi:10.1109/FOCS46700.2020.00012.
Kush D, Rossman B. Tree-depth and the formula complexity of subgraph isomorphism. Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. 2020. p. 31–42.

Published In

Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

DOI

ISSN

0272-5428

ISBN

9781728196213

Publication Date

November 1, 2020

Volume

2020-November

Start / End Page

31 / 42