Name
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 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. 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 (worst-case, uncolored) one. |
Year | Venue | Keywords |
|---|---|---|
2014 | SIAM J. Comput. | lower bound technique,logarithmic factor,subgraph isomorphism problem,ac0,linear-size monotone projection,trees (mathematics),bounded-depth circuits,treewidth,ac0, subgraph isomorphism, average-case complexity, treewidth,pattern matching,average-case version subgraph,computational complexity,disjoint union,graph theory,edge matching,average-case complexity,pattern tree-width,subgraph isomorphism,ac0 complexity,computer science,upper bound |
DocType | Volume | Issue |
Journal | 46 | 3 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yuan Li | 1 | 0 | 0.34 |
| Alexander A. Razborov | 2 | 0 | 0.68 |
| Benjamin Rossman | 3 | 4 | 4.28 |