On the AC0 Complexity of Subgraph Isomorphism

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 AC(0)-complexity of this problem, determined by the smallest possible exponent C(P) for which SUBGRAPH(P) possesses bounded-depth circuits of size n(C(P)+o(1)). Motivated by the previous research in the area, we also consider its "colorful" version SUBGRAPH(col)(P) in which the target graph G is V (P)-colored, and the average-case version SUBGRAPH(ave)(P) under the distribution G(n, n(-theta(P))), where theta(P) is the threshold exponent of P. Defining C-col(P) and C-ave(P) analogously to C(P), our main contributions can be summarized as follows. C-col(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 C-ave(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 SUBGRAPH(col)(Q) is reducible to SUBGRAPH(col)(P) via a linear-size monotone projection. At the same time, we show that there is no monotone projection whatsoever that reduces SUBGRAPH(M-3) to SUBGRAPH(P-3 + M-2) (P-3 is a path on 3 vertices, M-k 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.