Abstract
For any fixed graph G, the subgraph isomorphism problem asks whether an nvertex input graph has a subgraph isomorphic to G. A wellknown algorithm of Alon, Yuster and Zwick (1995) efficiently reduces this to the "colored" version of the problem, denoted GSUB, and then solves GSUB in time O(n^{tw(G)+1}) where tw(G) is the treewidth of G. Marx (2010) conjectured that GSUB 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 GSUB, Li, Razborov and Rossman (2017) proved an unconditional averagecase 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 GSUB 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 averagecase complexity of GSUB is n^{o(tw(G))} for certain families of graphs G such as hypercubes.
BibTeX  Entry
@InProceedings{rosenthal:LIPIcs:2019:11485,
author = {Gregory Rosenthal},
title = {{Beating Treewidth for AverageCase Subgraph Isomorphism}},
booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
pages = {24:124:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771290},
ISSN = {18688969},
year = {2019},
volume = {148},
editor = {Bart M. P. Jansen and Jan Arne Telle},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11485},
URN = {urn:nbn:de:0030drops114850},
doi = {10.4230/LIPIcs.IPEC.2019.24},
annote = {Keywords: subgraph isomorphism, averagecase complexity, AC^0, circuit complexity}
}
Keywords: 

subgraph isomorphism, averagecase complexity, AC^0, circuit complexity 
Collection: 

14th International Symposium on Parameterized and Exact Computation (IPEC 2019) 
Issue Date: 

2019 
Date of publication: 

04.12.2019 