Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2016.8
URN: urn:nbn:de:0030-drops-69199
URL: https://drops.dagstuhl.de/opus/volltexte/2017/6919/
Borradaile, Glencora ; Le, Hung
Optimal Dynamic Program for r-Domination Problems over Tree Decompositions
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{borradaile_et_al:LIPIcs:2017:6919,
author = {Glencora Borradaile and Hung Le},
title = {{Optimal Dynamic Program for r-Domination Problems over Tree Decompositions}},
booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
pages = {8:1--8:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-023-1},
ISSN = {1868-8969},
year = {2017},
volume = {63},
editor = {Jiong Guo and Danny Hermelin},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/6919},
URN = {urn:nbn:de:0030-drops-69199},
doi = {10.4230/LIPIcs.IPEC.2016.8},
annote = {Keywords: r-dominating set, Exponential Time Hypothesis, Dynamic Programming}
}
| Keywords: | r-dominating set, Exponential Time Hypothesis, Dynamic Programming | |
| Seminar: | 11th International Symposium on Parameterized and Exact Computation (IPEC 2016) | |
| Issue date: | 2017 | |
| Date of publication: | 09.02.2017 |
