Document Open Access Logo

Structural Parameters, Tight Bounds, and Approximation for (k,r)-Center

Authors Ioannis Katsikarelis, Michael Lampis, Vangelis Th. Paschos

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2017.50.pdf
  • Filesize: 0.53 MB
  • 13 pages

Document Identifiers

Author Details

Ioannis Katsikarelis
Michael Lampis
Vangelis Th. Paschos

Cite As Get BibTex

Ioannis Katsikarelis, Michael Lampis, and Vangelis Th. Paschos. Structural Parameters, Tight Bounds, and Approximation for (k,r)-Center. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 50:1-50:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ISAAC.2017.50

Abstract

In (k,r)-Center we are given a (possibly edge-weighted) graph and are asked to select at most k vertices (centers), so that all other vertices are at distance at most r from a center. In this paper we provide a number of tight fine-grained bounds on the complexity of this problem with respect to various standard graph parameters. Specifically:

- For any r>=1, we show an algorithm that solves the problem in O*((3r+1)^cw) time, where cw is the clique-width of the input graph, as well as a tight SETH lower bound matching this algorithm's performance. As a corollary, for r=1, this closes the gap that previously existed on the complexity of Dominating Set parameterized by cw.

- We strengthen previously known FPT lower bounds, by showing that (k,r)-Center is W[1]-hard parameterized by the input graph's vertex cover (if edge weights are allowed), or feedback vertex set, even if k is an additional parameter. Our reductions imply tight ETH-based lower bounds. Finally, we devise an algorithm parameterized by vertex cover for unweighted graphs.

- We show that the complexity of the problem parameterized by tree-depth is 2^Theta(td^2) by showing an algorithm of this complexity and a tight ETH-based lower bound.

We complement these mostly negative results by providing FPT approximation schemes parameterized by clique-width or treewidth which work efficiently independently of the values of k,r. In particular, we give algorithms which, for any epsilon>0, run in time O*((tw/epsilon)^O(tw)), O*((cw/epsilon)^O(cw)) and return a (k,(1+epsilon)r)-center, if a (k,r)-center exists, thus circumventing the problem's W-hardness.

Subject Classification

Keywords
  • FPT algorithms
  • Approximation
  • Treewidth
  • Clique-width
  • Domination

Metrics

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

References

  1. P.K. Agarwal and C.M. Procopiuc. Exact and approximation algorithms for clustering. Algorithmica, 33(2):201-226, 2002. Google Scholar
  2. J. Alber and R. Niedermeier. Improved tree decomposition based algorithms for domination-like problems. In LATIN, volume 2286 of LNCS, pages 613-628, 2002. Google Scholar
  3. E. Angel, E. Bampis, B. Escoffier, and M. Lampis. Parameterized power vertex cover. In WG, volume 9941 of LNCS, pages 97-108, 2016. Google Scholar
  4. A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto. Fourier meets möbius: fast subset convolution. In STOC, pages 67-74, 2007. Google Scholar
  5. H.L. Bodlaender. Treewidth: Characterizations, applications, and computations. In WG, volume 4271 of LNCS, pages 1-14. Springer, 2006. Google Scholar
  6. H.L. Bodlaender, J.R. Gilbert, H. Hafsteinsson, and T. Kloks. Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. J. Algorithms, 18(2):238-255, 1995. Google Scholar
  7. H.L. Bodlaender and T. Hagerup. Parallel algorithms with optimal speedup for bounded treewidth. SIAM J. Comput., 27(6):1725-1746, 1998. Google Scholar
  8. H.L. Bodlaender and A.M.C.A. Koster. Combinatorial optimization on graphs of bounded treewidth. Comput. J., 51(3):255-269, 2008. Google Scholar
  9. H.L. Bodlaender, E.J. van Leeuwen, J.M.M. van Rooij, and M. Vatshelle. Faster algorithms on branch and clique decompositions. In MFCS, volume 6281 of LNCS, pages 174-185, 2010. Google Scholar
  10. G. Borradaile and H. Le. Optimal dynamic program for r-domination problems over tree decompositions. In IPEC, volume 63, pages 8:1-8:23, 2016. Google Scholar
  11. A. Brandstädt and F.F. Dragan. A linear-time algorithm for connected r-domination and steiner tree on distance-hereditary graphs. Networks, 31(3):177-182, 1998. Google Scholar
  12. R.S. Coelho, P.F. S. Moura, and Y. Wakabayashi. The k-hop connected dominating set problem: hardness and polyhedra. Electronic Notes in Discrete Mathematics, 50:59-64, 2015. Google Scholar
  13. B. Courcelle, J.A. Makowsky, and U. Rotics. Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst., 33(2):125-150, 2000. Google Scholar
  14. B. Courcelle and S. Olariu. Upper bounds to the clique width of graphs. Discrete Applied Mathematics, 101(1-3):77-114, 2000. Google Scholar
  15. M. Cygan, F.V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  16. E.D. Demaine, F.V. Fomin, M.T. Hajiaghayi, and D.M. Thilikos. Fixed-parameter algorithms for (k, r)-center in planar graphs and map graphs. ACM Trans. Algorithms, 1(1):33-47, 2005. Google Scholar
  17. R.G. Downey and M.R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  18. D. Eisenstat, P.N. Klein, and C. Mathieu. Approximating k-center in planar graphs. In SODA, pages 617-627, 2014. Google Scholar
  19. T. Feder and D.H. Greene. Optimal algorithms for approximate clustering. In STOC, pages 434-444, 1988. Google Scholar
  20. A.E. Feldmann. Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs. In ICALP, volume 9135 of LNCS, 2015. Google Scholar
  21. J. Flum and M. Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. Google Scholar
  22. P.A. Golovach and Y. Villanger. Parameterized Complexity for Domination Problems on Degenerate Graphs. In WG, volume 5344 of LNCS, page 195–205, 2008. Google Scholar
  23. F. Gurski and E. Wanke. The tree-width of clique-width bounded graphs without K_n, n. In WG, volume 1928 of LNCS, pages 196-205, 2000. Google Scholar
  24. D.S. Hochbaum and D.B. Shmoys. A unified approach to approximation algorithms for bottleneck problems. J. ACM, 33(3):533-550, 1986. Google Scholar
  25. I.Katsikarelis, M. Lampis, and V.Th. Paschos. Structural parameters, tight bounds, and approximation for (k, r)-center. CoRR, abs/1704.08868, 2017. Google Scholar
  26. R. Impagliazzo and R. Paturi. On the complexity of k-sat. J. Comput. Syst. Sci., 62(2):367-375, 2001. Google Scholar
  27. R. Impagliazzo, R. Paturi, and F. Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. Google Scholar
  28. S. Khuller, R. Pless, and Y.J. Sussmann. Fault tolerant k-center problems. Theor. Comput. Sci., 242(1-2):237-245, 2000. Google Scholar
  29. S. Khuller and Y.J. Sussmann. The capacitated K-center problem. SIAM J. Discrete Math., 13(3):403-418, 2000. Google Scholar
  30. T. Kloks. Treewidth, Computations and Approximations, volume 842 of LNCS. Springer, 1994. Google Scholar
  31. S.O. Krumke. On a generalization of the p-center problem. Inf. Process. Lett., 56(2):67-71, 1995. Google Scholar
  32. M. Lampis. Parameterized approximation schemes using graph widths. In ICALP, volume 8572 of LNCS, pages 775-786. Springer, 2014. Google Scholar
  33. M. Lampis, K. Makino, V. Mitsou, and Y. Uno. Parameterized edge hamiltonicity. In WG, volume 8747 of LNCS, pages 348-359, 2014. Google Scholar
  34. A. Leitert and F.F. Dragan. Parameterized approximation algorithms for some location problems in graphs. CoRR, abs/1706.07475v1, 2017. Google Scholar
  35. D. Lokshtanov, D. Marx, and S. Saurabh. Known algorithms on graphs on bounded treewidth are probably optimal. In SODA, pages 777-789, 2011. Google Scholar
  36. D. Lokshtanov, N. Misra, G. Philip, M.S. Ramanujan, and S. Saurabh. Hardness of r-dominating set on graphs of diameter (r + 1). In IPEC, volume 8246 of LNCS, pages 255-267, 2013. Google Scholar
  37. D. Marx. Efficient approximation schemes for geometric problems? In ESA, volume 3669 of LNCS, pages 448-459, 2005. Google Scholar
  38. D. Marx. Parameterized complexity and approximation algorithms. Comput. J., 51(1):60-78, 2008. Google Scholar
  39. D. Moshkovitz. The projection games conjecture and the NP-hardness of ln n-approximating set-cover. Theory of Computing, 11:221-235, 2015. Google Scholar
  40. J. Nesetril and P. Ossona de Mendez. Tree-depth, subgraph coloring and homomorphism bounds. Eur. J. Comb., 27(6):1022-1041, 2006. Google Scholar
  41. S. Oum, S.H. Sæther, and M. Vatshelle. Faster algorithms for vertex partitioning problems parameterized by clique-width. Theor. Comput. Sci., 535:16-24, 2014. Google Scholar
  42. R. Panigrahy and S. Vishwanathan. An o(log* n) approximation algorithm for the asymmetric p-center problem. J. Algorithms, 27(2):259-268, 1998. Google Scholar
  43. P.J. Slater. R-domination in graphs. J. ACM, 23(3):446-450, 1976. Google Scholar
  44. J.A. Telle and A. Proskurowski. Practical algorithms on partial k-trees with an application to domination-like problems. In WADS, volume 709 of LNCS, pages 610-621, 1993. Google Scholar
  45. J.M.M. van Rooij, H.L. Bodlaender, and P. Rossmanith. Dynamic programming on tree decompositions using generalised fast subset convolution. In ESA, volume 5757 of LNCS, pages 566-577, 2009. Google Scholar
  46. V.V. Vazirani. Approximation algorithms. Springer, 2001. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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