On the AC0 complexity of subgraph isomorphism

Published

Journal Article

© 2017 Society for Industrial and Applied Mathematics. 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)+o(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: (1) Ccol(P) coincides with the treewidth of the pattern P up to a logarithmic factor. This shows that the previously known upper bound by Alon, Yuster, and Zwick [J. ACM, 42 (1995), pp. 844-856] is almost tight. (2) We give a characterization of Cave(P) in purely combinatorial terms up to a multiplicative factor of 2. This shows that the lower bound technique of Rossman [Proceedings of the 40th ACM Symposium on Theory of Computing, 2008, pp. 721-730] is essentially tight for any pattern P whatsoever. (3) 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 three 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 (worst-case, uncolored) one.

Full Text

Duke Authors

Cited Authors

  • Li, Y; Razborov, A; Rossman, B

Published Date

  • January 1, 2017

Published In

Volume / Issue

  • 46 / 3

Start / End Page

  • 936 - 971

Electronic International Standard Serial Number (EISSN)

  • 1095-7111

International Standard Serial Number (ISSN)

  • 0097-5397

Digital Object Identifier (DOI)

  • 10.1137/14099721X

Citation Source

  • Scopus