Marx, Dániel ;
Pilipczuk, Marcin
Subexponential Parameterized Algorithms for Graphs of Polynomial Growth
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^{11/(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 lowtreewidth 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^{11/(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^{11/(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^{11/depsilon}}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:159:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770491},
ISSN = {18688969},
year = {2017},
volume = {87},
editor = {Kirk Pruhs and Christian Sohler},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7816},
URN = {urn:nbn:de:0030drops78162},
doi = {10.4230/LIPIcs.ESA.2017.59},
annote = {Keywords: polynomial growth, subexponential algorithm, low treewidth pattern covering}
}
01.09.2017
Keywords: 

polynomial growth, subexponential algorithm, low treewidth pattern covering 
Seminar: 

25th Annual European Symposium on Algorithms (ESA 2017)

Issue date: 

2017 
Date of publication: 

01.09.2017 