Document Open Access Logo

Hierarchy of Transportation Network Parameters and Hardness Results

Author Johannes Blum

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2019.4.pdf
  • Filesize: 0.51 MB
  • 15 pages

Document Identifiers

Author Details

Johannes Blum
  • University of Konstanz, Germany

Cite As Get BibTex

Johannes Blum. Hierarchy of Transportation Network Parameters and Hardness Results. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.IPEC.2019.4

Abstract

The graph parameters highway dimension and skeleton dimension were introduced to capture the properties of transportation networks. As many important optimization problems like Travelling Salesperson, Steiner Tree or k-Center arise in such networks, it is worthwhile to study them on graphs of bounded highway or skeleton dimension.
We investigate the relationships between mentioned parameters and how they are related to other important graph parameters that have been applied successfully to various optimization problems. We show that the skeleton dimension is incomparable to any of the parameters distance to linear forest, bandwidth, treewidth and highway dimension and hence, it is worthwhile to study mentioned problems also on graphs of bounded skeleton dimension. Moreover, we prove that the skeleton dimension is upper bounded by the max leaf number and that for any graph on at least three vertices there are edge weights such that both parameters are equal.
Then we show that computing the highway dimension according to most recent definition is NP-hard, which answers an open question stated by Feldmann et al. [Andreas Emil Feldmann et al., 2015]. Finally we prove that on graphs G=(V,E) of skeleton dimension O(log^2 |V|) it is NP-hard to approximate the k-Center problem within a factor less than 2.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph theory
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Graph Parameters
  • Skeleton Dimension
  • Highway Dimension
  • k-Center

Metrics

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

Related Versions

References

  1. Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck. Highway Dimension and Provably Efficient Shortest Path Algorithms. J. ACM, 63(5):41:1-41:26, 2016. URL: https://doi.org/10.1145/2985473.
  2. Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, and Renato Fonseca F. Werneck. VC-Dimension and Shortest Path Algorithms. In Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP), pages 690-699, 2011. URL: https://doi.org/10.1007/978-3-642-22006-7_58.
  3. Ittai Abraham, Amos Fiat, Andrew V. Goldberg, and Renato Fonseca F. Werneck. Highway Dimension, Shortest Paths, and Provably Efficient Algorithms. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), pages 782-793, 2010. URL: https://doi.org/10.1137/1.9781611973075.64.
  4. Stefan Arnborg. Efficient Algorithms for Combinatorial Problems with Bounded Decomposability - A Survey. BIT, 25(1):2-23, 1985. Google Scholar
  5. Sanjeev Arora. Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and other Geometric Problems. J. ACM, 45(5):753-782, 1998. URL: https://doi.org/10.1145/290179.290180.
  6. Yair Bartal, Lee-Ad Gottlieb, and Robert Krauthgamer. The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme. SIAM J. Comput., 45(4):1563-1581, 2016. URL: https://doi.org/10.1137/130913328.
  7. H. Bast, Stefan Funke, and Domagoj Matijevic. Ultrafast Shortest-Path Queries via Transit Nodes. In The Shortest Path Problem, Proceedings of a DIMACS Workshop, volume 74 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 175-192. DIMACS/AMS, 2006. URL: https://doi.org/10.1090/dimacs/074/07.
  8. H. Bast, Stefan Funke, Domagoj Matijevic, Peter Sanders, and Dominik Schultes. In Transit to Constant Time Shortest-Path Queries in Road Networks. In Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 2007. URL: https://doi.org/10.1137/1.9781611972870.5.
  9. Reinhard Bauer, Tobias Columbus, Ignaz Rutter, and Dorothea Wagner. Search-space size in contraction hierarchies. Theor. Comput. Sci., 645:112-127, 2016. URL: https://doi.org/10.1016/j.tcs.2016.07.003.
  10. Amariah Becker, Philip N. Klein, and David Saulpic. Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension. In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, Proceedings of the 26th Annual European Symposium on Algorithms (ESA), volume 112 of LIPIcs, pages 8:1-8:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.8.
  11. Johannes Blum and Sabine Storandt. Computation and Growth of Road Network Dimensions. In Lusheng Wang and Daming Zhu, editors, Proceedings of the 24th International Computing and Combinatorics Conference (COCOON), volume 10976 of Lecture Notes in Computer Science, pages 230-241. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-94776-1_20.
  12. Hans L. Bodlaender. Dynamic Programming on Graphs with Bounded Treewidth. In Timo Lepistö and Arto Salomaa, editors, Proceedings of the 15th International Colloquium on Automata, Languages and Programming (ICALP), volume 317 of Lecture Notes in Computer Science, pages 105-118. Springer, 1988. URL: https://doi.org/10.1007/3-540-19488-6_110.
  13. Hans L. Bodlaender. A Partial k-Arboretum of Graphs with Bounded Treewidth. Theor. Comput. Sci., 209(1-2):1-45, 1998. URL: https://doi.org/10.1016/S0304-3975(97)00228-4.
  14. Kevin Cattell, Michael J. Dinneen, and Michael R. Fellows. A Simple Linear-Time Algorithm for Finding Path-Decompositions of Small Width. Inf. Process. Lett., 57(4):197-203, 1996. URL: https://doi.org/10.1016/0020-0190(95)00190-5.
  15. Ermelinda DeLaViña and Bill Waller. A note on a conjecture of Hansen et al. Unpublished manuscript, 2009. URL: http://cms.dt.uh.edu/faculty/delavinae/research/DelavinaWaller2009.pdf.
  16. Tomás Feder and Daniel H. Greene. Optimal Algorithms for Approximate Clustering. In Janos Simon, editor, Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), pages 434-444. ACM, 1988. URL: https://doi.org/10.1145/62212.62255.
  17. Andreas Emil Feldmann. Fixed-Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs. Algorithmica, 81(3):1031-1052, 2019. URL: https://doi.org/10.1007/s00453-018-0455-0.
  18. Andreas Emil Feldmann, Wai Shing Fung, Jochen Könemann, and Ian Post. A (1 + ε)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs. CoRR, abs/1502.04588, 2015. URL: http://arxiv.org/abs/1502.04588.
  19. Andreas Emil Feldmann, Wai Shing Fung, Jochen Könemann, and Ian Post. A (1+ε)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs. SIAM J. Comput., 47(4):1667-1704, 2018. URL: https://doi.org/10.1137/16M1067196.
  20. Andreas Emil Feldmann and Dániel Marx. The Parameterized Hardness of the k-Center Problem in Transportation Networks. In David Eppstein, editor, Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), volume 101 of LIPIcs, pages 19:1-19:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.SWAT.2018.19.
  21. Lee-Ad Gottlieb and Robert Krauthgamer. Proximity Algorithms for Nearly Doubling Spaces. SIAM J. Discrete Math., 27(4):1759-1769, 2013. URL: https://doi.org/10.1137/120874242.
  22. Dorit S. Hochbaum and David B. Shmoys. A unified approach to approximation algorithms for bottleneck problems. J. ACM, 33(3):533-550, 1986. URL: https://doi.org/10.1145/5925.5933.
  23. Haim Kaplan and Ron Shamir. Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques. SIAM J. Comput., 25(3):540-561, 1996. URL: https://doi.org/10.1137/S0097539793258143.
  24. Adrian Kosowski and Laurent Viennot. Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1462-1478. SIAM, 2017. Google Scholar
  25. Jan Plesník. On the computational complexity of centers locating in a graph. Aplikace matematiky, 25(6):445-452, 1980. URL: https://dml.cz/bitstream/handle/10338.dmlcz/103883/AplMat_25-1980-6_8.pdf.
  26. Manuel Sorge, Matthias Weller, Florent Foucaud, Ondřej Suchý, Pascal Ochem, Martin Vatshelle, and Gerhard J. Woeginger. The Graph Parameter Hierarchy. Unpublished manuscript, 2019. URL: https://manyu.pro/assets/parameter-hierarchy.pdf.
  27. Kunal Talwar. Bypassing the embedding: algorithms for low dimensional metrics. In László Babai, editor, Proceedings of the 36th Annual ACM Symposium on Theory of Computing (SODA), pages 281-290. ACM, 2004. URL: https://doi.org/10.1145/1007352.1007399.
  28. Vijay V. Vazirani. Approximation algorithms. Springer, 2001. URL: http://www.springer.com/computer/theoretical+computer+science/book/978-3-540-65367-7.
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