Document Open Access Logo

Characterizing Demand Graphs for (Fixed-Parameter) Shallow-Light Steiner Network

Authors Amy Babay, Michael Dinitz, Zeyu Zhang

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2018.33.pdf
  • Filesize: 0.75 MB
  • 22 pages

Document Identifiers

Author Details

Amy Babay
  • Johns Hopkins University, Baltimore, Maryland, USA
Michael Dinitz
  • Johns Hopkins University, Baltimore, Maryland, USA
Zeyu Zhang
  • Johns Hopkins University, Baltimore, Maryland, USA

Funding

Supported in part by NSF award 1535887.

Cite AsGet BibTex

Amy Babay, Michael Dinitz, and Zeyu Zhang. Characterizing Demand Graphs for (Fixed-Parameter) Shallow-Light Steiner Network. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 33:1-33:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.FSTTCS.2018.33

Abstract

We consider the Shallow-Light Steiner Network problem from a fixed-parameter perspective. Given a graph G, a distance bound L, and p pairs of vertices (s_1,t_1),...,(s_p,t_p), the objective is to find a minimum-cost subgraph G' such that s_i and t_i have distance at most L in G' (for every i in [p]). Our main result is on the fixed-parameter tractability of this problem for parameter p. We exactly characterize the demand structures that make the problem "easy", and give FPT algorithms for those cases. In all other cases, we show that the problem is W[1]-hard. We also extend our results to handle general edge lengths and costs, precisely characterizing which demands allow for good FPT approximation algorithms and which demands remain W[1]-hard even to approximate.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
Keywords
  • fixed-parameter tractable
  • network design
  • shallow-light steiner network
  • demand graphs

Metrics

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

Related Versions

References

  1. Amir Abboud and Greg Bodwin. Reachability Preservers: New Extremal Bounds and Approximation Algorithms. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pages 1865-1883, 2018. Google Scholar
  2. Amy Babay, Michael Dinitz, and Zeyu Zhang. Characterizing Demand Graphs for (Fixed-Parameter) Shallow-Light Steiner Network. arXiv preprint arXiv:1802.10566, 2018. Google Scholar
  3. Amy Babay, Emily Wagner, Michael Dinitz, and Yair Amir. Timely, Reliable, and Cost-Effective Internet Transport Service Using Dissemination Graphs. In 37th IEEE International Conference on Distributed Computing Systems, ICDCS 2017, pages 1-12, 2017. Google Scholar
  4. 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 Foundations of Computer Science (FOCS), 2017 IEEE 58th Annual Symposium on, pages 743-754. IEEE, 2017. Google Scholar
  5. Moses Charikar, Chandra Chekuri, To-yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, and Ming Li. Approximation algorithms for directed Steiner problems. Journal of Algorithms, 33(1):73-91, 1999. Google Scholar
  6. 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 (TALG), 7(2):18, 2011. Google Scholar
  7. Rajesh Chitnis, Andreas Emil Feldmann, and Pasin Manurangsi. Parameterized Approximation Algorithms for Directed Steiner Network Problems. arXiv preprint arXiv:1707.06499, 2017. Google Scholar
  8. Eden Chlamtác, Michael Dinitz, Guy Kortsarz, and Bundit Laekhanukit. Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pages 534-553, 2017. Google Scholar
  9. Stuart E Dreyfus and Robert A Wagner. The Steiner problem in graphs. Networks, 1(3):195-207, 1971. Google Scholar
  10. Jon Feldman and Matthias Ruhl. The directed Steiner network problem is tractable for a constant number of terminals. SIAM Journal on Computing, 36(2):543-561, 2006. Google Scholar
  11. Andreas Emil Feldmann and Dániel Marx. The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, volume 55 of LIPIcs, pages 27:1-27:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  12. Michael R Fellows, Danny Hermelin, Frances Rosamond, and Stéphane Vialette. On the parameterized complexity of multiple-interval graph problems. Theoretical Computer Science, 410(1):53-61, 2009. Google Scholar
  13. Longkun Guo, Kewen Liao, and Hong Shen. On the shallow-light steiner tree problem. In Parallel and Distributed Computing, Applications and Technologies (PDCAT), 2014 15th International Conference on, pages 56-60. IEEE, 2014. Google Scholar
  14. Mohammad Taghi Hajiaghayi, Guy Kortsarz, and Mohammad R Salavatipour. Approximating buy-at-bulk and shallow-light k-Steiner trees. Algorithmica, 53(1):89-103, 2009. Google Scholar
  15. Refael Hassin. Approximation schemes for the restricted shortest path problem. Mathematics of Operations research, 17(1):36-42, 1992. Google Scholar
  16. Guy Kortsarz and David Peleg. Approximating shallow-light trees. Technical report, Association for Computing Machinery, New York, NY (United States), 1997. Google Scholar
  17. Dean H Lorenz and Danny Raz. A simple efficient approximation scheme for the restricted shortest path problem. Operations Research Letters, 28(5):213-219, 2001. Google Scholar
  18. Joseph Naor and Baruch Schieber. Improved approximations for shallow-light spanning trees. In Foundations of Computer Science, 1997. Proceedings., 38th Annual Symposium on, pages 536-541. IEEE, 1997. Google Scholar
  19. Leonid Zosin and Samir Khuller. On directed Steiner trees. In Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, pages 59-63. Society for Industrial and Applied Mathematics, 2002. 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