Beating Treewidth for Average-Case Subgraph Isomorphism

Abstract

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 $\Omega (n^{\mathrm{const}\cdot tw(G)})$ and, assuming the Exponential Time Hypothesis, proved a lower bound of $\Omega (n^{\mathrm{const}\cdot emb(G)})$ for a certain graph parameter $emb(G)\ge \Omega (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\kappa (G)+\mathrm{const}})$ and $\Omega (n^{\kappa (G)})$ for a different graph parameter $\kappa (G)\ge \Omega (tw(G)/\log tw(G))$. Our contributions are as follows. First, we prove that $emb(G)$ is $O(\kappa (G))$ for all graphs $G$. Next, we show that $\kappa (G)$ can be asymptotically less than $tw(G)$; for example, if $G$ is a hypercube then $\kappa (G)$ is $\Theta (tw(G)/\sqrt{\log tw(G)})$. 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^{\kappa (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