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

Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.