Math @ Duke

Publications [#348677] of Benjamin Rossman
Papers Published
 Li, Y; Razborov, A; Rossman, B, On the AC^{0} complexity of subgraph isomorphism,
Siam Journal on Computing, vol. 46 no. 3
(January, 2017),
pp. 936971 [doi]
(last updated on 2022/05/19)
Abstract: 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 AC0complexity of this problem, determined by the smallest possible exponent C(P) for which Subgraph(P) possesses boundeddepth 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 averagecase 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. 844856] 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. 721730] 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 linearsize 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 wellbehaved than the standard (worstcase, uncolored) one.


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

