License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2017.59
URN: urn:nbn:de:0030-drops-78162
URL: http://drops.dagstuhl.de/opus/volltexte/2017/7816/
Go to the corresponding LIPIcs Volume Portal


Marx, Dániel ; Pilipczuk, Marcin

Subexponential Parameterized Algorithms for Graphs of Polynomial Growth

pdf-format:
LIPIcs-ESA-2017-59.pdf (0.6 MB)


Abstract

We show that for a number of parameterized problems for which only 2^{O(k)} n^{O(1)} time algorithms are known on general graphs, subexponential parameterized algorithms with running time 2^{O(k^{1-1/(1+d)} log^2 k)} n^{O(1)} are possible for graphs of polynomial growth with growth rate (degree) d, that is, if we assume that every ball of radius r contains only O(r^d) vertices. The algorithms use the technique of low-treewidth pattern covering, introduced by Fomin et al. [FOCS 2016] for planar graphs; here we show how this strategy can be made to work for graphs of polynomial growth. Formally, we prove that, given a graph G of polynomial growth with growth rate d and an integer k, one can in randomized polynomial time find a subset A of V(G) such that on one hand the treewidth of G[A] is O(k^{1-1/(1+d)} log k), and on the other hand for every set X of vertices of size at most k, the probability that X is a subset of A is 2^{-O(k^{1-1/(1+d)} log^2 k)}. Together with standard dynamic programming techniques on graphs of bounded treewidth, this statement gives subexponential parameterized algorithms for a number of subgraph search problems, such as Long Path or Steiner Tree, in graphs of polynomial growth. We complement the algorithm with an almost tight lower bound for Long Path: unless the Exponential Time Hypothesis fails, no parameterized algorithm with running time 2^{k^{1-1/d-epsilon}}n^{O(1)} is possible for any positive epsilon and any integer d >= 3.

BibTeX - Entry

@InProceedings{marx_et_al:LIPIcs:2017:7816,
  author =	{D{\'a}niel Marx and Marcin Pilipczuk},
  title =	{{Subexponential Parameterized Algorithms for Graphs of Polynomial Growth}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{59:1--59:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Kirk Pruhs and Christian Sohler},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7816},
  URN =		{urn:nbn:de:0030-drops-78162},
  doi =		{10.4230/LIPIcs.ESA.2017.59},
  annote =	{Keywords: polynomial growth, subexponential algorithm, low treewidth pattern covering}
}

Keywords: polynomial growth, subexponential algorithm, low treewidth pattern covering
Seminar: 25th Annual European Symposium on Algorithms (ESA 2017)
Issue Date: 2017
Date of publication: 31.08.2017


DROPS-Home | Fulltext Search | Imprint Published by LZI