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^{1-\frac{1}{1+\delta }}{\log }^{2}k)}{n}^{O(1)}$ are possible for graphs of polynomial growth with growth rate (degree) $\delta$, that is, if we assume that every ball of radius $r$ contains only $O(r^{\delta })$ 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 with polynomial growth. Formally, we prove that, given a graph $G$ of polynomial growth with growth rate $\delta$ and an integer $k$, one can in randomized polynomial time find a subset $A\subseteq V(G)$ such that on one hand the treewidth of $G[A]$ is $O(k^{1-\frac{1}{1+\delta }}\log k)$, and on the other hand for every set $X\subseteq V(G)$ of size at most $k$, the probability that $X\subseteq A$ is $2^{-O(k^{1-\frac{1}{1+\delta }}{\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-\frac{1}{\delta }-\epsilon }}{n}^{O(1)}$ is possible for any $\epsilon >0$ and an integer $\delta \ge 3$.

References in corpus (1)

• Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs