For any fixed graph $G$, the subgraph isomorphism problem asks whether an $n$-vertex input graph has a subgraph isomorphic to $G$. A well-known algorithm of Alon, Yuster and Zwick (1995) efficiently reduces this to the "colored" version of the problem, denoted $G$-$\mathsf{SUB}$, and then solves $G$-$\mathsf{SUB}$ in time $O(n^{tw(G)+1})$ where $tw(G)$ is the treewidth of $G$. Marx (2010) conjectured that $G$-$\mathsf{SUB}$ requires time $��(n^{\mathrm{const}\cdot tw(G)})$ and, assuming the Exponential Time Hypothesis, proved a lower bound of $��(n^{\mathrm{const}\cdot emb(G)})$ for a certain graph parameter $emb(G) \ge ��(tw(G)/\log tw(G))$. With respect to the size of $\mathrm{AC}^0$ circuits solving $G$-$\mathsf{SUB}$ in the average case, Li, Razborov and Rossman (2017) proved (unconditional) upper and lower bounds of $O(n^{2��(G)+\mathrm{const}})$ and $��(n^{��(G)})$ for a different graph parameter $��(G) \ge ��(tw(G)/\log tw(G))$. Our contributions are as follows. First, we prove that $emb(G)$ is $O(��(G))$ for all graphs $G$. Next, we show that $��(G)$ can be asymptotically less than $tw(G)$; for example, if $G$ is a hypercube then $��(G)$ is $��\big(tw(G)\big/\sqrt{\log tw(G)}\big)$. This implies that the average-case complexity of $G$-$\mathsf{SUB}$ is $n^{o(tw(G))}$ when $G$ is a hypercube. Finally, we construct $\mathrm{AC}^0$ circuits of size $O(n^{��(G)+\mathrm{const}})$ that solve $G$-$\mathsf{SUB}$ in the average case, closing the gap between the upper and lower bounds of Li et al.

31 pages. International Symposium on Parameterized and Exact Computation (IPEC) 2019