2026-07-26T01:42:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6919 2024-03-06T10:38:47Z ddc:004 open_access

Optimal Dynamic Program for r-Domination Problems over Tree Decompositions Borradaile, Glencora Le, Hung r-dominating set Exponential Time Hypothesis Dynamic Programming There has been recent progress in showing that the exponential dependence on treewidth in dynamic programming algorithms for solving NP-hard problems is optimal under the Strong Exponential Time Hypothesis (SETH). We extend this work to r-domination problems. In r-dominating set, one wishes 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)^tw n) time algorithm for r-dominating set and a randomized O((2r+2)^tw n^{O(1)}) time algorithm for connected r-dominating set in n-vertex graphs of treewidth tw. We show that the running time dependence on r and tw is the best possible under SETH. This adds to earlier observations that a "+1" in the denominator is required for connectivity constraints. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Glencora Borradaile and Hung Le 2017 Is Part Of LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2016.8 urn:nbn:de:0030-drops-69199 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.8 eng https://creativecommons.org/licenses/by/3.0/legalcode