Document Open Access Logo

Parameterized Algorithms and Data Reduction for Safe Convoy Routing

Authors René van Bevern , Till Fluschnik, Oxana Yu. Tsidulko

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2018.10.pdf
  • Filesize: 0.52 MB
  • 19 pages

Document Identifiers

Author Details

René van Bevern
  • Department of Mechanics and Mathematics, Novosibirsk State University, Ulitsa Pirogova 2, 630090 Novosibirsk, Russian Federation
  • Sobolev Institute of Mathematics of the Siberian Branch of the Russian Academy of Sciences, Prospekt Akademika Koptyuga 4, 630090 Novosibirsk, Russian Federation
Till Fluschnik
  • Institut für Softwaretechnik und Theoretische Informatik, TU Berlin, Ernst-Reuter-Platz 7, 10587 Berlin, Germany
Oxana Yu. Tsidulko
  • Sobolev Institute of Mathematics of the Siberian Branch of the Russian Academy of Sciences, Prospekt Akademika Koptyuga 4, 630090 Novosibirsk, Russian Federation
  • Department of Mechanics and Mathematics, Novosibirsk State University, Ulitsa Pirogova 2, 630090 Novosibirsk, Russian Federation

Funding

Till Fluschnik was supported by the German Research Foundation, grant NI 369/18. René van Bevern and Oxana Yu. Tsidulko were supported by the Russian Foundation for Basic Research (RFBR), grant 18-501-12031 NNIOunderscore a, while working on Sections 2.2, 2.3, 3.3, and 3.2. While working on Sections 2.1 and 3.1, René van Bevern was supported by RFBR grant 16-31-60007 molunderscore aunderscore dk and Oxana Yu. Tsidulko was supported by the Ministry of Science and Higher Education of the Russian Federation under the 5-100 Excellence Programme.

Cite As Get BibTex

René van Bevern, Till Fluschnik, and Oxana Yu. Tsidulko. Parameterized Algorithms and Data Reduction for Safe Convoy Routing. In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/OASIcs.ATMOS.2018.10

Abstract

We study a problem that models safely routing a convoy through a transportation network, where any vertex adjacent to the travel path of the convoy requires additional precaution: Given a graph G=(V,E), two vertices s,t in V, and two integers k,l, we search for a simple s-t-path with at most k vertices and at most l neighbors. We study the problem in two types of transportation networks: graphs with small crossing number, as formed by road networks, and tree-like graphs, as formed by waterways. For graphs with constant crossing number, we provide a subexponential 2^O(sqrt n)-time algorithm and prove a matching lower bound. We also show a polynomial-time data reduction algorithm that reduces any problem instance to an equivalent instance (a so-called problem kernel) of size polynomial in the vertex cover number of the input graph. In contrast, we show that the problem in general graphs is hard to preprocess. Regarding tree-like graphs, we obtain a 2^O(tw) * l^2 * n-time algorithm for graphs of treewidth tw, show that there is no problem kernel with size polynomial in tw, yet show a problem kernel with size polynomial in the feedback edge number of the input graph.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • NP-hard problem
  • fixed-parameter tractability
  • problem kernelization
  • shortest path
  • secluded solution

Metrics

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

Related Versions

References

  1. Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck. Route planning in transportation networks. In Algorithm Engineering: Selected Results and Surveys, volume 9220 of Lecture Notes in Computer Science, pages 19-80. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-319-49487-6_2.
  2. René van Bevern, Till Fluschnik, George B. Mertzios, Hendrik Molter, Manuel Sorge, and Ondřej Suchý. The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs. Discrete Optimzation, 2018. In press, available on arXiv:1606.09000v5. URL: http://dx.doi.org/10.1016/j.disopt.2018.05.002.
  3. René van Bevern, Christian Komusiewicz, and Manuel Sorge. A parameterized approximation algorithm for the mixed and windy capacitated arc routing problem: Theory and experiments. Networks, 70(3):262-278, 2017. WARP 2 special issue. URL: http://dx.doi.org/10.1002/net.21742.
  4. René van Bevern, Rolf Niedermeier, Manuel Sorge, and Mathias Weller. Complexity of arc routing problems. In Arc Routing: Problems, Methods, and Applications, volume 20 of MOS-SIAM Series on Optimization. SIAM, 2014. URL: http://dx.doi.org/10.1137/1.9781611973679.ch2.
  5. Hans-Joachim Böckenhauer, Juraj Hromkovič, Joachim Kneis, and Joachim Kupke. The parameterized approximability of TSP with deadlines. Theory of Computing Systems, 41(3):431-444, 2007. URL: http://dx.doi.org/10.1007/s00224-007-1347-x.
  6. Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Information and Computation, 243:86-111, 2015. URL: http://dx.doi.org/10.1016/j.ic.2014.12.008.
  7. Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin. On problems without polynomial kernels. Journal of Computer and System Sciences, 75(8):423-434, 2009. URL: http://dx.doi.org/10.1016/j.jcss.2009.04.001.
  8. Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michał Pilipczuk. A c^k n 5-approximation algorithm for treewidth. SIAM Journal on Computing, 45(2):317-378, 2016. URL: http://dx.doi.org/10.1137/130947374.
  9. Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Kernelization lower bounds by cross-composition. SIAM Journal on Discrete Mathematics, 28(1):277-305, 2014. URL: http://dx.doi.org/10.1137/120880240.
  10. Drago Bokal, Gasper Fijavz, and Bojan Mohar. The minor crossing number. SIAM Journal on Discrete Mathematics, 20(2):344-356, 2006. URL: http://dx.doi.org/10.1137/05062706X.
  11. Shiri Chechik, Matthew P. Johnson, Merav Parter, and David Peleg. Secluded connectivity problems. Algorithmica, 79(3):708-741, 2017. URL: http://dx.doi.org/10.1007/s00453-016-0222-z.
  12. 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.
  13. Erik D. Demaine and Mohammadtaghi Hajiaghayi. Linearity of grid minors in treewidth with applications through bidimensionality. Combinatorica, 28(1):19-36, 2008. URL: http://dx.doi.org/10.1007/s00493-008-2140-4.
  14. Reinhard Diestel. Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer, 4th edition, 2010. URL: http://dx.doi.org/10.1007/978-3-662-53622-3.
  15. Frederic Dorn, Hannes Moser, Rolf Niedermeier, and Mathias Weller. Efficient algorithms for Eulerian Extension and Rural Postman. SIAM Journal on Discrete Mathematics, 27(1):75-94, 2013. URL: http://dx.doi.org/10.1137/110834810.
  16. Rod G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Springer, 2013. URL: http://dx.doi.org/10.1007/978-1-4471-5559-1.
  17. Michael Etscheid, Stefan Kratsch, Matthias Mnich, and Heiko Röglin. Polynomial kernels for weighted problems. Journal of Computer and System Sciences, 84(Supplement C):1-10, 2017. URL: http://dx.doi.org/10.1016/j.jcss.2016.06.004.
  18. Stefan Fafianie, Hans L. Bodlaender, and Jesper Nederlof. Speeding up dynamic programming with representative sets: An experimental evaluation of algorithms for steiner tree on tree decompositions. Algorithmica, 71(3):636-660, 2015. URL: http://dx.doi.org/10.1007/s00453-014-9934-0.
  19. Michael R. Fellows, Ariel Kulik, Frances A. Rosamond, and Hadas Shachnai. Parameterized approximation via fidelity preserving transformations. Journal of Computer and System Sciences, 93:30-40, 2018. URL: http://dx.doi.org/10.1016/j.jcss.2017.11.001.
  20. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Springer, 2006. URL: http://dx.doi.org/10.1007/3-540-29953-X.
  21. Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, and Alexander S. Kulikov. Parameterized complexity of secluded connectivity problems. Theory of Computing Systems, 61(3):795-819, 2017. URL: http://dx.doi.org/10.1007/s00224-016-9717-x.
  22. András Frank and Éva Tardos. An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica, 7(1):49-65, 1987. URL: http://dx.doi.org/10.1007/BF02579200.
  23. Achille Giacometti. River networks. In Complex Networks, Encyclopedia of Life Support Systems (EOLSS), pages 155-180. EOLSS Publishers/UNESCO, 2010. Google Scholar
  24. Petr A. Golovach, Pinar Heggernes, Paloma T. Lima, and Pedro Montealegre. Finding connected secluded subgraphs. In Proceedings of the 12th International Symposium on Parameterized and Exact Computation, IPEC 2017, September 6-8, 2017, Vienna, Austria, volume 89 of LIPIcs, pages 18:1-18:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2017.18.
  25. Jiong Guo and Rolf Niedermeier. Invitation to data reduction and problem kernelization. ACM SIGACT News, 38(1):31-45, 2007. URL: http://dx.doi.org/10.1145/1233481.1233493.
  26. G. Gutin and V. Patel. Parameterized traveling salesman problem: Beating the average. SIAM Journal on Discrete Mathematics, 30(1):220-238, 2016. URL: http://dx.doi.org/10.1137/140980946.
  27. Gregory Gutin, Mark Jones, and Bin Sheng. Parameterized complexity of the k-arc chinese postman problem. Journal of Computer and System Sciences, 84:107-119, 2017. URL: http://dx.doi.org/10.1016/j.jcss.2016.07.006.
  28. Gregory Gutin, Mark Jones, and Magnus Wahlström. The mixed chinese postman problem parameterized by pathwidth and treedepth. SIAM Journal on Discrete Mathematics, 30(4):2177-2205, 2016. URL: http://dx.doi.org/10.1137/15M1034337.
  29. Gregory Gutin, Gabriele Muciaccia, and Anders Yeo. Parameterized complexity of k-Chinese Postman Problem. Theoretical Computer Science, 513:124-128, 2013. URL: http://dx.doi.org/10.1016/j.tcs.2013.10.012.
  30. Gregory Gutin, Magnus Wahlström, and Anders Yeo. Rural Postman parameterized by the number of components of required edges. Journal of Computer and System Sciences, 83(1):121-131, 2017. URL: http://dx.doi.org/10.1016/j.jcss.2016.06.001.
  31. Danny Hermelin, Stefan Kratsch, Karolina Sołtys, Magnus Wahlström, and Xi Wu. A completeness theory for polynomial (turing) kernelization. Algorithmica, 71(3):702-730, 2015. URL: http://dx.doi.org/10.1007/s00453-014-9910-8.
  32. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. URL: http://dx.doi.org/10.1006/jcss.2001.1774.
  33. Philip N. Klein and Daniel Marx. A subexponential parameterized algorithm for Subset TSP on planar graphs. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'14), pages 1812-1830. Society for Industrial and Applied Mathematics, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.131.
  34. Stefan Kratsch. Recent developments in kernelization: A survey. Bulletin of the EATCS, 113, 2014. URL: http://eatcs.org/beatcs/index.php/beatcs/article/view/285.
  35. Stefan Kratsch and Magnus Wahlström. Compression via matroids: A randomized polynomial kernel for odd cycle transversal. ACM Transactions on Algorithms, 10(4):20:1-20:15, 2014. URL: http://dx.doi.org/10.1145/2635810.
  36. Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. Lossy kernelization. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017), pages 224-237. ACM, 2017. URL: http://dx.doi.org/10.1145/3055399.3055456.
  37. Max-Jonathan Luckow and Till Fluschnik. On the computational complexity of length- and neighborhood-constrained path problems. Available on arXiv:1808.02359, 2018. Google Scholar
  38. Neeldhara Misra, Venkatesh Raman, and Saket Saurabh. Lower bounds on kernelization. Discrete Optimization, 8(1):110-128, 2011. URL: http://dx.doi.org/10.1016/j.disopt.2010.10.001.
  39. Rolf Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006. URL: http://dx.doi.org/10.1093/acprof:oso/9780198566076.001.0001.
  40. Janos Pach, Rados Radoicic, Gabor Tardos, and Geza Toth. Improving the crossing lemma by finding more crossings in sparse graphs. Discrete & Computational Geometry, 36(4):527-552, 2006. URL: http://dx.doi.org/10.1007/s00454-006-1264-9.
  41. Manuel Sorge, René van Bevern, Rolf Niedermeier, and Mathias Weller. From few components to an Eulerian graph by adding arcs. In Proceedings of the 37th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'11), volume 6986 of Lecture Notes in Computer Science, pages 307-318. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-25870-1_28.
  42. Manuel Sorge, René van Bevern, Rolf Niedermeier, and Mathias Weller. A new view on Rural Postman based on Eulerian Extension and Matching. Journal of Discrete Algorithms, 16:12-33, 2012. URL: http://dx.doi.org/10.1016/j.jda.2012.04.007.
  43. K. Wagner. Über eine Eigenschaft der ebenen Komplexe. Mathematische Annalen, 114(1):570-590, 1937. URL: http://dx.doi.org/10.1007/BF01594196.
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