Subexponential parameterized algorithms for graphs of polynomial growth

DOI10.4230/LIPICS.ESA.2017.59zbMATH Open1442.68178arXiv1610.07778OpenAlexW2963153697MaRDI QIDQ5111748FDOQ5111748

Authors: Dániel Marx, Marcin Pilipczuk 

Publication date: 27 May 2020

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-frac11+delta}lo{g}^{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^{d}elta)$ 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 $AsubseteqV(G)$ such that on one hand the treewidth of $G[A]$ is $O(k^{1-frac11+delta}logk)$, and on the other hand for every set $XsubseteqV(G)$ of size at most $k$, the probability that $XsubseteqA$ is $2^{-O(k^{1-frac11+delta}lo{g}^{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-frac1delta-varepsilon}}{n}^{O(1)}$ is possible for any $varepsilon>0$ and an integer $deltageq3$.

Full work available at URL: https://arxiv.org/abs/1610.07778

Recommendations

• Sublinear-time algorithms for approximating graph parameters
• Subexponential parameterized algorithms
• Subexponential Parameterized Algorithms
• Approximating graphs with polynomial growth
• Approximation algorithms for polynomial-expansion and low-density graphs
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• scientific article; zbMATH DE number 7651188
• Subexponential parameterized algorithms and kernelization on almost chordal graphs
• Polynomial time algorithms for two classes of subgraph problem
• Subexponential parameterized algorithms for bounded-degree connected subgraph problems on planar graphs

zbMATH Keywords

subexponential algorithmpolynomial growthlow treewidth pattern covering

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
• Which problems have strongly exponential complexity?
• Title not available (Why is that?)
• Title not available (Why is that?)
• Parameterized Algorithms
• Sparsity. Graphs, structures, and algorithms
• Low diameter graph decompositions
• Subexponential algorithms for partial cover problems
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Subexponential parameterized algorithms
• Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
• Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs
• Linearity of grid minors in treewidth with applications through bidimensionality
• Probabilistic quorums for dynamic systems
• Fast sub-exponential algorithms and compactness in planar graphs
• LATIN 2004: Theoretical Informatics
• Graph Drawing
• Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)
• Routing with Improved Communication-Space Trade-Off
• Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time
• A subexponential parameterized algorithm for Subset TSP on planar graphs
• The limited blessing of low dimensionality
• Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering

Cited In (8)

• Surprising Applications of Treewidth Bounds for Planar Graphs
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• Subexponential parameterized algorithms
• On the existence of subexponential parameterized algorithms
• Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
• Algorithms and Turing kernels for detecting and counting small patterns in unit disk graphs
• Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
• Sublinear-time algorithms for approximating graph parameters

This page was built for publication: Subexponential parameterized algorithms for graphs of polynomial growth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111748)