Skip to main content

On the AC0 complexity of subgraph isomorphism

Publication ,  Conference
Li, Y; Razborov, A; Rossman, B
Published in: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
December 7, 2014

Let P be a fixed graph (hereafter called a "pattern"), and let SUBGRAPH(P) denote the problem of deciding whether a given graph G contains a subgraph isomorphic to P. We are interested in AC0-complexity of this problem, determined by the smallest possible exponent C(P) for which SUBGRAPH(P) possesses bounded-depth circuits of size nC(P)+σ(1). Motivated by the previous research in the area, we also consider its "colorful" version SUBGRAPHcol(P) in which the target graph G is V(P)-colored, and the average-case version SUBGRAPHave(P) under the distribution G(n, n θ(P)), where è(P) is the threshold exponent of P. Defining Ccol(P) and Cave(P) analogously to C(P), our main contributions can be summarized as follows. Ccol(P) coincides with the tree-width of the pattern P within a logarithmic factor. This shows that the previously known upper bound by Alon, Yuster, Zwick [3] is almost tight. We give a characterization of Cave(P) in purely combinatorial terms within a multiplicative factor of 2. This shows that the lower bound technique of Rossman [21] is essentially tight, for any pattern P whatsoever. We prove that if Q is a minor of P then SUBGRAPHcol(Q) is reducible to SUBGRAPHcol(P) via a linear-size monotone projection. At the same time, we show that there is no monotone projection whatsoever that reduces SUBGRAPH(M3) to SUBGRAPH(P3 +M2) (P3 is a path on 3 vertices, Mk is a matching with k edges, and "+" stands for the disjoint union). This result strongly suggests that the colorful version of the subgraph isomorphism problem is much better structured and well-behaved than the standard (worstcase, uncolored) one.

Duke Scholars

Published In

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

DOI

ISSN

0272-5428

ISBN

9781479965175

Publication Date

December 7, 2014

Start / End Page

344 / 353
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Li, Y., Razborov, A., & Rossman, B. (2014). On the AC0 complexity of subgraph isomorphism. In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS (pp. 344–353). https://doi.org/10.1109/FOCS.2014.44
Li, Y., A. Razborov, and B. Rossman. “On the AC0 complexity of subgraph isomorphism.” In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, 344–53, 2014. https://doi.org/10.1109/FOCS.2014.44.
Li Y, Razborov A, Rossman B. On the AC0 complexity of subgraph isomorphism. In: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. 2014. p. 344–53.
Li, Y., et al. “On the AC0 complexity of subgraph isomorphism.” Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2014, pp. 344–53. Scopus, doi:10.1109/FOCS.2014.44.
Li Y, Razborov A, Rossman B. On the AC0 complexity of subgraph isomorphism. Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. 2014. p. 344–353.

Published In

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

DOI

ISSN

0272-5428

ISBN

9781479965175

Publication Date

December 7, 2014

Start / End Page

344 / 353