Document Open Access Logo

Optimal Dynamic Program for r-Domination Problems over Tree Decompositions

Authors Glencora Borradaile, Hung Le

PDF

File

Thumbnail PDF
PDF
LIPIcs.IPEC.2016.8.pdf
  • Filesize: 0.59 MB
  • 23 pages

Document Identifiers

Subject Classification

Keywords
  • r-dominating set
  • Exponential Time Hypothesis
  • Dynamic Programming

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Glencora Borradaile and Hung Le. Optimal Dynamic Program for r-Domination Problems over Tree Decompositions. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 8:1-8:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.IPEC.2016.8

Author Details

Glencora Borradaile
Hung Le

References

  1. B. Baker. Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM, 41(1):153-180, 1994. URL: http://dx.doi.org/10.1145/174644.174650.
  2. H. L. Bodlaender, M. Cygan, S. Kratsch, and J. Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. In Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'13, pages 196-207, 2013. URL: http://dx.doi.org/10.1007/978-3-642-39206-1_17.
  3. H. L. Bodlaender and B. A. Fluiter. Reduction algorithms for graphs of small treewidth. Information and Computation, 167(2):86-119, 2001. URL: http://dx.doi.org/10.1006/inco.2000.2958.
  4. G. Borradaile, E. Demaine, and S. Tazari. Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs. Algorithmica, 68(2):287-311, 2014. URL: http://dx.doi.org/10.1007/s00453-012-9662-2.
  5. G. Borradaile, P. Klein, and C. Mathieu. An O(n log n) approximation scheme for Steiner tree in planar graphs. ACM Transactions on Algorithms, 5(3):31:1-31:31, 2009. URL: http://dx.doi.org/10.1145/1541885.1541892.
  6. M. Cygan, J. Nederlof, M. Pilipczuk, J. M. M. van Rooij M. Pilipczuk, and J. O. Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS'11, pages 150-159, 2011. URL: http://dx.doi.org/10.1109/FOCS.2011.23.
  7. E. Demaine, M. Hajiaghayi, and B. Mohar. Approximation algorithms via contraction decomposition. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'07, pages 278-287, 2007. Google Scholar
  8. E. D. Demaine, F. V. Fomin, M. Hajiaghayi, and D. M. Thilikos. Fixed-parameter algorithms for the (k, r)-center in planar graphs and map graphs. In Proceedings of the 30th International Conference on Automata, Languages and Programming, ICALP'03, pages 829-844, 2003. URL: http://dx.doi.org/10.1007/3-540-45061-0_65.
  9. D. Eisenstat, P. N. Klein, and C. Mathieu. Approximating k-center in planar graphs. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'14, pages 617-627, 2014. Google Scholar
  10. D. Eppstein. Diameter and treewidth in minor-closed graph families. Algorithmica, 27(3):275-291, 2000. URL: http://dx.doi.org/10.1007/s004530010020.
  11. F. V. Fomin, D. Lokshtanov, and S. Saurabh. Efficient computation of representative sets with applications in parameterized and exact algorithms. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'14, pages 142-151, 2014. Google Scholar
  12. R. Impagliazzo and R. Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367-375, 2001. URL: http://dx.doi.org/10.1006/jcss.2000.1727.
  13. P. N. Klein. A linear-time approximation scheme for TSP in undirected planar graphs with edge-weights. SIAM Journal on Computing, 37(6):1926-1952, 2008. URL: http://dx.doi.org/10.1137/060649562.
  14. Ton Kloks, editor. Treewidth, Computations and Approximations, volume 842. Springer Berlin Heidelberg, 1994. URL: http://dx.doi.org/10.1007/BFb0045375.
  15. D. Lokshtanov, D. Marx, and S. Saurabh. Known algorithms on graphs of bounded treewidth are probably optimal. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'11, pages 777-789, 2011. Google Scholar
  16. N. Robertson and P. D. Seymour. Graph minors. X. obstructions to tree-decomposition. Journal of Combinatorial Theory, Series B, 52(2):153-190, 1991. URL: http://dx.doi.org/10.1016/0095-8956(91)90061-N.
  17. A. Takahashi, S. Ueno, and Y. Kajitani. Mixed searching and proper-path-width. Theoretical Computer Science, 137(2):253-268, 1995. URL: http://dx.doi.org/10.1007/3-540-54945-5_50.
  18. L. G. Valiant and V. V. Vazirani. NP is as easy as detecting unique solutions. Theoretical Computer Science, 47(0):85-93, 1986. URL: http://dx.doi.org/10.1016/0304-3975(86)90135-0.
  19. J. M. M. van Rooij, H. L. Bodlaender, and P. Rossmanith. Dynamic programming on tree decompositions using generalised fast subset convolution. In Proceedings of 17th European Symposium on Algorithms, ESA'09, pages 566-577, 2009. URL: http://dx.doi.org/10.1007/978-3-642-04128-0_51.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact