A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps

Authors Raul Lopes , Ignasi Sau



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2020.68.pdf
  • Filesize: 0.6 MB
  • 15 pages

Document Identifiers

Author Details

Raul Lopes
  • Departamento de Computação, Universidade Federal do Ceará, Fortaleza, Brazil
  • LIRMM, Université de Montpellier, France
Ignasi Sau
  • LIRMM, Université de Montpellier, CNRS, France

Cite AsGet BibTex

Raul Lopes and Ignasi Sau. A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 68:1-68:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.MFCS.2020.68

Abstract

In the Directed Disjoint Paths problem, we are given a digraph D and a set of requests {(s₁, t₁), …, (s_k, t_k)}, and the task is to find a collection of pairwise vertex-disjoint paths {P₁, …, P_k} such that each P_i is a path from s_i to t_i in D. This problem is NP-complete for fixed k = 2 and W[1]-hard with parameter k in DAGs. A few positive results are known under restrictions on the input digraph, such as being planar or having bounded directed tree-width, or under relaxations of the problem, such as allowing for vertex congestion. Good news are scarce, however, for general digraphs. In this article we propose a novel global congestion metric for the problem: we only require the paths to be "disjoint enough", in the sense that they must behave properly not in the whole graph, but in an unspecified large part of it. Namely, in the Disjoint Enough Directed Paths problem, given an n-vertex digraph D, a set of k requests, and non-negative integers d and s, the task is to find a collection of paths connecting the requests such that at least d vertices of D occur in at most s paths of the collection. We study the parameterized complexity of this problem for a number of choices of the parameter, including the directed tree-width of D. Among other results, we show that the problem is W[1]-hard in DAGs with parameter d and, on the positive side, we give an algorithm in time 𝒪(n^{d+2} ⋅ k^{d⋅ s}) and a kernel of size d ⋅ 2^{k-s}⋅ binom(k,s) + 2k in general digraphs. This latter result has consequences for the Steiner Network problem: we show that it is FPT parameterized by the number k of terminals and d, where d = n - c and c is the size of the solution.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Parameterized complexity
  • directed disjoint paths
  • congestion
  • dual parameterization
  • kernelization
  • directed tree-width

Metrics

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

References

  1. Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx, and Roman Rabinovich. Routing with congestion in acyclic digraphs. Information Processing Letters, 151, 2019. URL: https://doi.org/10.1016/j.ipl.2019.105836.
  2. Júlio Araújo, Victor A. Campos, Carlos Vinícius G. C. Lima, Vinícius Fernandes dos Santos, Ignasi Sau, and Ana Silva. Dual Parameterization of Weighted Coloring. In Proc. of the 13th International Symposium on Parameterized and Exact Computation, (IPEC), volume 115 of LIPIcs, pages 12:1-12:14, 2018. URL: https://doi.org/10.4230/LIPIcs.IPEC.2018.12.
  3. Manu Basavaraju, Mathew C. Francis, M. S. Ramanujan, and Saket Saurabh. Partially polynomial kernels for set cover and test cover. SIAM Journal on Discrete Mathematics, 30(3):1401-1423, 2016. URL: https://doi.org/10.1137/15M1039584.
  4. Khristo N. Boyadzhiev. Close Encounters with the Stirling Numbers of the Second Kind. Mathematics Magazine, 85(4):252-266, 2012. URL: https://doi.org/10.4169/math.mag.85.4.252.
  5. Rajesh Hemant Chitnis, MohammadTaghi Hajiaghayi, and Dániel Marx. Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset. SIAM Journal on Computing, 42(4):1674-1696, 2013. URL: https://doi.org/10.1137/12086217X.
  6. Benny Chor, Mike Fellows, and David W. Juedes. Linear Kernels in Linear Time, or How to Save k Colors in O(n²) Steps. In Proc. of the 30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 3353 of LNCS, pages 257-269, 2004. URL: https://doi.org/10.1007/978-3-540-30559-0_22.
  7. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  8. Marek Cygan, Daniel Marx, Marcin Pilipczuk, and Michal Pilipczuk. The Planar Directed k-Vertex-Disjoint Paths Problem Is Fixed-Parameter Tractable. In Proc. of the IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), volume 1, pages 197-206, 2013. URL: https://doi.org/10.1109/FOCS.2013.29.
  9. Rod Downey and Michael. R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  10. Rong-chii Duh and Martin Fürer. Approximation of k-Set Cover by Semi-Local Optimization. In Proc. of the 29th Annual ACM Symposium on the Theory of Computing (STOC), pages 256-264, 1997. URL: https://doi.org/10.1145/258533.258599.
  11. Katherine Edwards, Irene Muzi, and Paul Wollan. Half-integral linkages in highly connected directed graphs. In Proc. of the 25th Annual European Symposium on Algorithms (ESA), 2017, pages 36:1-36:12, 2017. URL: https://doi.org/10.4230/LIPIcs.ESA.2017.36.
  12. Andreas Emil Feldmann and Dániel Marx. The complexity landscape of fixed-parameter directed Steiner network problems. In Proc. of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), volume 55, pages 27:1-27:14, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.27.
  13. Steven Fortune, John Hopcroft, and James Wyllie. The directed subgraph homeomorphism problem. Theoretical Computer Science, 10(2):111-121, 1980. URL: https://doi.org/10.1016/0304-3975(80)90009-2.
  14. Thor Johnson, Neil Robertson, Paul Seymour, and Robin Thomas. Directed tree-width. Journal of Combinatorial Theory, Series B, 82(01):138-154, 2001. URL: https://doi.org/10.1006/jctb.2000.2031.
  15. Mark Jones, Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, and Ondřej Suchý. Parameterized Complexity of Directed Steiner Tree on Sparse Graphs. SIAM Journal on Discrete Mathematics, 31(2):1294-1327, 2017. URL: https://doi.org/10.1137/15M103618X.
  16. Ken-ichi Kawarabayashi, Yusuke Kobayashi, and Stephan Kreutzer. An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem. In Proc. of the 46th ACM Symposium on Theory of Computing (STOC), pages 70-78, 2014. URL: https://doi.org/10.1145/2591796.2591876.
  17. Ken-ichi Kawarabayashi and Stephan Kreutzer. The Directed Grid Theorem. In Proc. of the 47th Annual ACM Symposium on Theory of Computing (STOC), pages 655-664, 2015. URL: https://doi.org/10.1145/2746539.2746586.
  18. Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, and Magnus Wahlström. Fixed-parameter tractability of multicut in directed acyclic graphs. SIAM Journal on Discrete Mathematics, 29(1):122-144, 2015. URL: https://doi.org/10.1137/120904202.
  19. James F. Lynch. The equivalence of theorem proving and the interconnection problem. ACM SIGDA Newsletter, 5(3):31-36, 1975. URL: https://doi.org/10.1145/1061425.1061430.
  20. Karl Menger. Zur allgemeinen kurventheorie. Fundamenta Mathematicae, 10(1):96-115, 1927. URL: http://eudml.org/doc/211191.
  21. Daniel Mölle, Stefan Richter, and Peter Rossmanith. Enumerate and expand: improved algorithms for connected vertex cover and tree cover. Theory of Computing Systems, 43(2):234-253, 2008. URL: https://doi.org/10.1007/s00224-007-9089-3.
  22. Marcin Pilipczuk, MichałPilipczuk, Piotr Sankowski, and Erik Jan Van Leeuwen. Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs. ACM Transactions on Algorithms, 14(4):53:1-53:73, 2018. URL: https://doi.org/10.1145/3239560.
  23. Neil Robertson and Paul Seymour. Graph minors. XIII. The disjoint paths problem. Journal of Combinatorial Theory, Series B, 63(1):65-110, 1995. URL: https://doi.org/doi.org/10.1006/jctb.1995.1006.
  24. Alexander Schrijver. Finding k disjoint paths in a directed planar graph. SIAM Journal on Computing, 23(4):780-788, 1994. URL: https://doi.org/10.1137/S0097539792224061.
  25. Aleksandrs Slivkins. Parameterized tractability of edge-disjoint paths on directed acyclic graphs. SIAM Journal on Discrete Mathematics, 24(1):146-157, 2010. URL: https://doi.org/10.1137/070697781.
  26. Carsten Thomassen. Highly connected non-2-linked digraphs. Combinatorica, 11(4):393-395, 1991. URL: https://doi.org/10.1007/BF01275674.
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