Document Open Access Logo

Parameterized Approximation Algorithms for Bidirected Steiner Network Problems

Authors Rajesh Chitnis, Andreas Emil Feldmann, Pasin Manurangsi

PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.20.pdf
  • Filesize: 0.52 MB
  • 16 pages

Document Identifiers

Author Details

Rajesh Chitnis
  • University of Warwick, UK
Andreas Emil Feldmann
  • Charles University, Prague, Czechia.
Pasin Manurangsi
  • University of California, Berkeley, USA.

Funding

  • Chitnis, Rajesh: Supported by ERC grant 2014-CoG 647557. Part of this work was done while at Weizmann Institute of Science, Israel and supported by Israel Science Foundation grant #897/13
  • Feldmann, Andreas Emil: Supported by the Czech Science Foundation GAČR (grant #17-10090Y), and by the Center for Foundations of Modern Computer Science (Charles Univ. project UNCE/SCI/004).
  • Manurangsi, Pasin: This work was done while the author was visiting Weizmann Institute of Science.

Cite AsGet BibTex

Rajesh Chitnis, Andreas Emil Feldmann, and Pasin Manurangsi. Parameterized Approximation Algorithms for Bidirected Steiner Network Problems. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 20:1-20:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ESA.2018.20

Abstract

The Directed Steiner Network (DSN) problem takes as input a directed edge-weighted graph G=(V,E) and a set {D}subseteq V x V of k demand pairs. The aim is to compute the cheapest network N subseteq G for which there is an s -> t path for each (s,t)in {D}. It is known that this problem is notoriously hard as there is no k^{1/4-o(1)}-approximation algorithm under Gap-ETH, even when parameterizing the runtime by k [Dinur & Manurangsi, ITCS 2018]. In light of this, we systematically study several special cases of DSN and determine their parameterized approximability for the parameter k. For the bi-DSN_Planar problem, the aim is to compute a planar optimum solution N subseteq G in a bidirected graph G, i.e. for every edge uv of G the reverse edge vu exists and has the same weight. This problem is a generalization of several well-studied special cases. Our main result is that this problem admits a parameterized approximation scheme (PAS) for k. We also prove that our result is tight in the sense that (a) the runtime of our PAS cannot be significantly improved, and (b) it is unlikely that a PAS exists for any generalization of bi-DSN_Planar, unless FPT=W[1]. Additionally we study several generalizations of bi-DSN_Planar and obtain upper and lower bounds on obtainable runtimes parameterized by k. One important special case of DSN is the Strongly Connected Steiner Subgraph (SCSS) problem, for which the solution network N subseteq G needs to strongly connect a given set of k terminals. It has been observed before that for SCSS a parameterized 2-approximation exists when parameterized by k [Chitnis et al., IPEC 2013]. We show a tight inapproximability result: under Gap-ETH there is no (2-{epsilon})-approximation algorithm parameterized by k (for any epsilon>0). To the best of our knowledge, this is the first example of a W[1]-hard problem admitting a non-trivial parameterized approximation factor which is also known to be tight! Additionally we show that when restricting the input of SCSS to bidirected graphs, the problem remains NP-hard but becomes FPT for k.

Subject Classification

ACM Subject Classification
  • Theory of computation → Routing and network design problems
  • Theory of computation → Fixed parameter tractability
Keywords
  • Directed Steiner Network
  • Strongly Connected Steiner Subgraph
  • Parameterized Approximations
  • Bidirected Graphs
  • Planar Graphs

Metrics

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

Related Versions

References

  1. Ajit Agrawal, Philip Klein, and R Ravi. When trees collide: An approximation algorithm for the generalized Steiner problem on networks. SIAM Journal on Computing, 24(3):440-456, 1995. Google Scholar
  2. Benny Applebaum. Exponentially-Hard Gap-CSP and Local PRG via Local Hardcore Functions. In FOCS 2017, pages 836-847, 2017. URL: http://dx.doi.org/10.1109/FOCS.2017.82.
  3. Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, and Grigory Yaroslavtsev. Approximation algorithms for spanner problems and directed steiner forest. Information and Computation, 222:93-107, 2013. Google Scholar
  4. Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., and Pasin Manurangsi. Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH. To appear in ICALP 2018, 2018. URL: http://arxiv.org/abs/1803.09717.
  5. Edouard Bonnet, Bruno Escoffier, EunJung Kim, and Vangelis T. Paschos. On subexponential and FPT-time inapproximability. In IPEC, pages 54-65, 2013. Google Scholar
  6. Al Borchers and Ding-Zhu Du. The k-Steiner Ratio in Graphs. SIAM Journal on Computing, 26(3):857-869, 1997. Google Scholar
  7. Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, and Laura Sanità. Steiner tree approximation via iterative randomized rounding. Journal of the ACM, 60(1):6, 2013. Google Scholar
  8. Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, and Luca Trevisan. From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More. In To appear in FOCS, 2017. Google Scholar
  9. Chandra Chekuri, Guy Even, Anupam Gupta, and Danny Segev. Set connectivity problems in undirected graphs and the directed Steiner network problem. ACM Transactions on Algorithms, 7(2):18, 2011. Google Scholar
  10. W-T Chen and N-F Huang. The strongly connecting problem on multihop packet radio networks. IEEE Transactions on Communications, 37(3):293-295, 1989. Google Scholar
  11. Yijia Chen and Bingkai Lin. The constant inapproximability of the parameterized dominating set problem. In FOCS, pages 505-514, 2016. Google Scholar
  12. Rajesh Chitnis, Andreas Emil Feldmann, and Pasin Manurangsi. Parameterized Approximation Algorithms for Directed Steiner Network Problems. CoRR, abs/1707.06499, 2017. URL: http://arxiv.org/abs/1707.06499.
  13. Rajesh Chitnis, MohammadTaghi Hajiaghayi, and Guy Kortsarz. Fixed-parameter and approximation algorithms: A new look. In IPEC, pages 110-122, 2013. Google Scholar
  14. Rajesh Chitnis, MohammadTaghi Hajiaghayi, and Dániel Marx. Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions). In SODA, pages 1782-1801, 2014. Google Scholar
  15. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3.
  16. Irit Dinur. Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. Electronic Colloquium on Computational Complexity (ECCC), 23:128, 2016. Google Scholar
  17. Irit Dinur and Pasin Manurangsi. ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network. In ITCS, pages 36:1-36:20, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.ITCS.2018.36.
  18. Yevgeniy Dodis and Sanjeev Khanna. Design networks with bounded pairwise distance. In STOC 1999, pages 750-759, 1999. Google Scholar
  19. S. E. Dreyfus and R. A. Wagner. The Steiner problem in graphs. Networks, 1(3):195-207, 1971. Google Scholar
  20. Ding-Zhu Du, Yanjun Zhang, and Qing Feng. On better heuristic for Euclidean Steiner minimum trees. In FOCS 1991, pages 431-439, 1991. Google Scholar
  21. Pavel Dvorák, Andreas Emil Feldmann, Dusan Knop, Tomás Masarík, Tomas Toufar, and Pavel Veselý. Parameterized approximation schemes for steiner trees with small number of steiner vertices. In STACS, pages 26:1-26:15, 2018. Google Scholar
  22. Eduard Eiben, Dušan Knop, Fahad Panolan, and Ondřej Suchý. Complexity of the steiner network problem with respect to the number of terminals. arXiv preprint, 2018. URL: http://arxiv.org/abs/1802.08189.
  23. Eduard Eiben, Mithilesh Kumar, Amer E Mouawad, and Fahad Panolan. Lossy kernels for connected dominating set on sparse graphs. arXiv preprint, 2017. URL: http://arxiv.org/abs/1706.09339.
  24. Jon Feldman and Matthias Ruhl. The directed Steiner network problem is tractable for a constant number of terminals. SIAM J. Comput., 36(2):543-561, 2006. Google Scholar
  25. Moran Feldman, Guy Kortsarz, and Zeev Nutov. Improved approximation algorithms for directed steiner forest. J. Comput. Syst. Sci., 78(1):279-292, 2012. URL: http://dx.doi.org/10.1016/j.jcss.2011.05.009.
  26. Andreas Emil Feldmann. Fixed parameter approximations for k-center problems in low highway dimension graphs. In ICALP, pages 588-600, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47666-6_47.
  27. Andreas Emil Feldmann and Dániel Marx. The complexity landscape of fixed-parameter directed steiner network problems. CoRR, abs/1707.06808, 2017. URL: http://arxiv.org/abs/1707.06808.
  28. Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering. In FOCS, pages 515-524, 2016. URL: http://dx.doi.org/10.1109/FOCS.2016.62.
  29. Greg N Frederickson and Joseph Ja’Ja’. Approximation algorithms for several graph augmentation problems. SIAM Journal on Computing, 10(2):270-283, 1981. Google Scholar
  30. E. N. Gilbert and H. O. Pollak. Steiner minimal trees. SIAM Journal on Applied Mathematics, 16(1):1-29, 1968. Google Scholar
  31. Jiong Guo, Rolf Niedermeier, and Ondrej Suchý. Parameterized complexity of arc-weighted directed Steiner problems. SIAM J. Discrete Math., 25(2):583-599, 2011. Google Scholar
  32. Eran Halperin and Robert Krauthgamer. Polylogarithmic inapproximability. In STOC, pages 585-594, 2003. Google Scholar
  33. Russell Impagliazzo and Ramamohan Paturi. On the Complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367-375, 2001. Google Scholar
  34. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which Problems Have Strongly Exponential Complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. Google Scholar
  35. Giuseppe F Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen. Improved algorithms for min cut and max flow in undirected planar graphs. In STOC 2011, pages 313-322, 2011. Google Scholar
  36. Marek Karpinski and Alexander Zelikovsky. New approximation algorithms for the Steiner tree problem. Journal of Combinatorial Optimization, 1(1):47-65, 1997. Google Scholar
  37. Karthik C. S., Bundit Laekhanukit, and Pasin Manurangsi. On the Parameterized Complexity of Approximating Dominating Set. To appear in STOC 2018, 2017. URL: http://arxiv.org/abs/1711.11029.
  38. Hervé Kerivin and A Ridha Mahjoub. Design of survivable networks: A survey. Networks, 46(1):1-21, 2005. Google Scholar
  39. Philip Klein, Serge A. Plotkin, and Satish Rao. Excluded Minors, Network Decomposition, and Multicommodity Flow. In STOC 1993, pages 682-690, 1993. Google Scholar
  40. Philip N. Klein and Dániel Marx. Solving Planar k -Terminal Cut in O(n^c√k) Time. In ICALP, pages 569-580, 2012. URL: http://dx.doi.org/10.1007/978-3-642-31594-7_48.
  41. Philip N. Klein and Dániel Marx. A subexponential parameterized algorithm for Subset TSP on planar graphs. In SODA, pages 1812-1830, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.131.
  42. R. Krithika, Pranabendu Misra, Ashutosh Rai, and Prafullkumar Tale. Lossy kernels for graph contraction problems. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016), volume 65, pages 23:1-23:14, Dagstuhl, Germany, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2016.23.
  43. Nhat X Lam, Trac N Nguyen, Min Kyung An, and Dung T Huynh. Dual power assignment optimization and fault tolerance in WSNs. Journal of Combinatorial Optimization, 30(1):120-138, 2015. Google Scholar
  44. Michael Lampis. Parameterized approximation schemes using graph widths. In ICALP, pages 775-786, 2014. Google Scholar
  45. James Lee. A simpler proof of the KPR theorem, 2012. URL: https://tcsmath.org/2012/01/11/a-simpler-proof-of-the-kpr-theorem/.
  46. Daniel Lokshtanov, Fahad Panolan, MS Ramanujan, and Saket Saurabh. Lossy Kernelization. In STOC, pages 224-237, 2017. Google Scholar
  47. Daniel Lokshtanov, Saket Saurabh, and Magnus Wahlström. Subexponential Parameterized Odd Cycle Transversal on Planar Graphs. In FSTTCS, pages 424-434, 2012. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2012.424.
  48. Pasin Manurangsi and Prasad Raghavendra. A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs. In ICALP, pages 78:1-78:15, 2017. Google Scholar
  49. Dániel Marx. Parameterized complexity and approximation algorithms. The Computer Journal, 51(1):60-78, 2008. Google Scholar
  50. Dániel Marx. A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals. In ICALP, pages 677-688, 2012. URL: http://dx.doi.org/10.1007/978-3-642-31594-7_57.
  51. Dániel Marx, Marcin Pilipczuk, and Michał Pilipczuk. On subexponential parameterized algorithms for Steiner Tree and Directed Subset TSP on planar graphs. arXiv preprint arXiv:1707.1707.02190, 2017. Google Scholar
  52. Dániel Marx and Michal Pilipczuk. Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams. In ESA, pages 865-877, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48350-3_72.
  53. Daniel Mölle, Stefan Richter, and Peter Rossmanith. A faster algorithm for the steiner tree problem. In STACS, pages 561-570, 2006. Google Scholar
  54. Marcin Pilipczuk, Michal Pilipczuk, Piotr Sankowski, and Erik Jan van Leeuwen. Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs. In STACS, pages 353-364, 2013. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2013.353.
  55. Marcin Pilipczuk, Michal Pilipczuk, Piotr Sankowski, and Erik Jan van Leeuwen. Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs. In FOCS, pages 276-285, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.37.
  56. Hans Jürgen Prömel and Angelika Steger. A new approximation algorithm for the Steiner tree problem with performance ratio 5/3. Journal of Algorithms, 36:89-101, 2000. Google Scholar
  57. Ram Ramanathan and Regina Rosales-Hain. Topology control of multihop wireless networks using transmit power adjustment. In INFOCOM, volume 2, pages 404-413, 2000. Google Scholar
  58. Gabriel Robins and Alexander Zelikovsky. Tighter bounds for graph Steiner tree approximation. SIAM Journal on Discrete Mathematics, 19(1):122-134, 2005. Google Scholar
  59. Sebastian Siebertz. Lossy kernels for connected distance-r domination on nowhere dense graph classes. arXiv preprint, 2017. URL: http://arxiv.org/abs/1707.09819.
  60. Vijay Virkumar Vazirani. Approximation Algorithms. Springer-Verlag, 2001. Google Scholar
  61. Chen Wang, Myung-Ah Park, James Willson, Yongxi Cheng, Andras Farago, and Weili Wu. On approximate optimal dual power assignment for biconnectivity and edge-biconnectivity. Theoretical Computer Science, 396(1-3):180-190, 2008. Google Scholar
  62. Andreas Wiese. A (1 + ε)-approximation for unsplittable flow on a path in fixed-parameter running time. In ICALP 2017, pages 67:1-67:13, 2017. Google Scholar
  63. Alexander Zelikovsky. An 11/6-approximation algorithm for the network Steiner problem. Algorithmica, 9:463-470, 1993. 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 Imprint Privacy Contact