TR14-145 Authors: Yuan Li, Alexander Razborov, Benjamin Rossman

Publication: 4th November 2014 04:24

Downloads: 1504

Keywords:

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.

1. $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 is almost

tight.

2. 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 is essentially tight, for any

pattern $P$ whatsoever.

3. 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.