Math @ Duke

Publications [#348684] of Benjamin Rossman
Papers Published
 Li, Y; Razborov, A; Rossman, B, On the AC^{0} complexity of subgraph isomorphism,
Annual Symposium on Foundations of Computer Science (Proceedings)
(December, 2014),
pp. 344353, ISBN 9781479965175 [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)+σ(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. Ccol(P) coincides with the treewidth 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 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 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 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

