Optimal dynamic program for r-domination problems over tree decompositions

DOI10.4230/LIPICS.IPEC.2016.8MaRDI QIDQ4634391zbMATH OpenOpenAlexFDO

Authors Glencora Borradaile, Hung Le

Publication date 10 April 2018

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

zbMATH Keywords

\(r\)-dominating setdynamic programmingexponential time hypothesis

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Dynamic programming (90C39)

Abstract: There has been recent progress in showing that the exponential dependence on treewidth in dynamic programming algorithms for solving NP-hard problems are optimal under the Strong Exponential Time Hypothesis (SETH). We extend this work to $r$-domination problems. In $r$-dominating set, one wished to find a minimum subset $S$ of vertices such that every vertex of $G$ is within $r$ hops of some vertex in $S$. In connected $r$-dominating set, one additionally requires that the set induces a connected subgraph of $G$. We give a $O((2r+1{)}^{mathrmtw}n)$ time algorithm for $r$-dominating set and a $O((2r+2{)}^{mathrmtw}{n}^{O(1)})$ time algorithm for connected $r$-dominating set in $n$-vertex graphs of treewidth $mathrmtw$. We show that the running time dependence on $r$ and $mathrmtw$ is the best possible under SETH. This adds to earlier observations that a "+1" in the denominator is required for connectivity constraints.

Recommendations

• scientific article; zbMATH DE number 2086260
• Practical algorithms on partial k-trees with an application to domination-like problems
• Publication:4934237
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Known algorithms on graphs of bounded treewidth are probably optimal

Cited in

(32)

• The k-hop connected dominating set problem: approximation and hardness
• Structurally parameterized \(d\)-scattered set
• A generic convolution algorithm for join operations on tree decompositions
• A linear-time algorithm for minimum \(k\)-hop dominating set of a cactus graph
• Structural parameters, tight bounds, and approximation for \((k, r)\)-center
• Finer tight bounds for coloring on clique-width
• New results on directed edge dominating set
• On the k-hop domination numbers of spanning trees of unicyclic graphs
• Fast Algorithms for Join Operations on Tree Decompositions
• Finer tight bounds for coloring on clique-width
• A dynamic domination problem in trees
• scientific article; zbMATH DE number 7278055 (Why is no real title available?)
• Nonserial Dynamic Programming and Tree Decomposition in Discrete Optimization
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• scientific article; zbMATH DE number 7764100 (Why is no real title available?)
• Guarding polyominoes under \(k\)-hop visibility
• Towards tight bounds for the graph homomorphism problem parameterized by cutwidth via asymptotic matrix parameters
• Fundamental problems on bounded-treewidth graphs: the real source of hardness
• A tight Monte-Carlo algorithm for Steiner tree parameterized by clique-width
• Tight complexity bounds for counting generalized dominating sets in bounded-treewidth graphs. I: Algorithmic results
• Tight complexity bounds for counting generalized dominating sets in bounded-treewidth graphs. II: Hardness results
• Towards exact structural thresholds for parameterized complexity
• Parameterized complexity of (d, r)-domination via modular decomposition
• Guarding polyominoes under k-hop visibility
• Structural parameterizations for two bounded degree problems revisited
• Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
• List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
• Hitting meets packing: how hard can it be?
• Residue domination in bounded-treewidth graphs
• Independence and domination on bounded-treewidth graphs: integer, rational, and irrational distances
• Tight bounds for some classical problems parameterized by cutwidth
• Dynamic programming and planarity: improved tree-decomposition based algorithms

This page was built for publication: Optimal dynamic program for \(r\)-domination problems over tree decompositions

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