License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2019.24
URN: urn:nbn:de:0030-drops-114850
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11485/
Go to the corresponding LIPIcs Volume Portal

Rosenthal, Gregory

Beating Treewidth for Average-Case Subgraph Isomorphism

pdf-format:
LIPIcs-IPEC-2019-24.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{rosenthal:LIPIcs:2019:11485,
  author =	{Gregory Rosenthal},
  title =	{{Beating Treewidth for Average-Case Subgraph Isomorphism}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{24:1--24:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Bart M. P. Jansen and Jan Arne Telle},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2019/11485},
  URN =		{urn:nbn:de:0030-drops-114850},
  doi =		{10.4230/LIPIcs.IPEC.2019.24},
  annote =	{Keywords: subgraph isomorphism, average-case complexity, AC^0, circuit complexity}
}

Keywords: subgraph isomorphism, average-case 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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI