Beating Treewidth for Average-Case Subgraph Isomorphism.

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 et al. (J ACM 42(4):844–856, 1995. https://doi.org/10.1145/210332.210337 ) efficiently reduces this to the “colored” version of the problem, denoted $$G{\text{-}}{\mathsf {SUB}}$$ , and then solves $$G{\text{-}}{\mathsf {SUB}}$$ in time $$O(n^{{\textit{tw}}(G)+1})$$ where $${\textit{tw}}(G)$$ is the treewidth of G. Marx (Theory Comput 6(1):85–112, 2010. https://doi.org/10.4086/toc.2010.v006a005 ) conjectured that $$G{\text{-}}{\mathsf {SUB}}$$ requires time $$\varOmega (n^{{{\mathrm {const}}}\cdot {\textit{tw}}(G)})$$ and, assuming the Exponential Time Hypothesis, proved a lower bound of $$\varOmega (n^{{{\mathrm {const}}}\cdot {\textit{emb}}(G)})$$ for a certain graph parameter $${\textit{emb}}(G) \ge \varOmega ({\textit{tw}}(G)/\log {\textit{tw}}(G))$$ . With respect to the size of $${{\mathrm {AC}}}^0$$ circuits solving $$G{\text{-}}{\mathsf {SUB}}$$ in the average case, Li et al. (SIAM J Comput 46(3):936–971, 2017. https://doi.org/10.1137/14099721X ) proved (unconditional) upper and lower bounds of $$O(n^{2\kappa (G)+{{\mathrm {const}}}})$$ and $$\varOmega (n^{\kappa (G)})$$ for a different graph parameter $$\kappa (G) \ge \varOmega ({\textit{tw}}(G)/\log {\textit{tw}}(G))$$ . Our contributions are as follows. First, we prove that $${\textit{emb}}(G)$$ is $$O(\kappa (G))$$ for all graphs G. Next, we show that $$\kappa (G)$$ can be asymptotically less than $${\textit{tw}}(G)$$ ; for example, if G is a hypercube then $$\kappa (G)$$ is $$\varTheta \left( {\textit{tw}}(G)\big /\sqrt{\log {\textit{tw}}(G)}\right) $$ . This implies that the average-case complexity of $$G{\text{-}}{\mathsf {SUB}}$$ is $$n^{o({\textit{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{\text{-}}{\mathsf {SUB}}$$ in the average case, closing the gap between the upper and lower bounds of Li et al.