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-SUB, and then solves G-SUB in time O(n^{tw(G)+1}) where tw(G) is the treewidth of G. Marx (2010) conjectured that G-SUB requires time Omega(n^{const * tw(G)}) and, assuming the Exponential Time Hypothesis, proved a lower bound of Omega(n^{const * emb(G)}) for a certain graph parameter emb(G) = Omega(tw(G)/log tw(G)). With respect to the size of AC^0 circuits solving G-SUB, Li, Razborov and Rossman (2017) proved an unconditional average-case lower bound of Omega(n^{kappa(G)}) for a different graph parameter kappa(G) = Omega(tw(G)/log tw(G)).
Our contributions are as follows. First, we show that emb(G) is at most 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)}). Finally, we construct AC^0 circuits of size O(n^{kappa(G)+const}) that solve G-SUB in the average case, on a variety of product distributions. This improves an O(n^{2 kappa(G)+const}) upper bound of Li et al., and shows that the average-case complexity of G-SUB is n^{o(tw(G))} for certain families of graphs G such as hypercubes.