2026-07-26T16:44:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7816 2024-03-06T10:41:22Z ddc:004 open_access

Subexponential Parameterized Algorithms for Graphs of Polynomial Growth Marx, Dániel Pilipczuk, Marcin polynomial growth subexponential algorithm low treewidth pattern covering 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dániel Marx and Marcin Pilipczuk 2017 Is Part Of LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2017.59 urn:nbn:de:0030-drops-78162 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.59 eng https://creativecommons.org/licenses/by/3.0/legalcode