Document Open Access Logo

New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness

Authors Krzysztof Fleszar, Matthias Mnich, Joachim Spoerhase

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.42.pdf
  • Filesize: 0.59 MB
  • 17 pages

Document Identifiers

Author Details

Krzysztof Fleszar
Matthias Mnich
Joachim Spoerhase

Cite AsGet BibTex

Krzysztof Fleszar, Matthias Mnich, and Joachim Spoerhase. New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 42:1-42:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ESA.2016.42

Abstract

We study the classical NP-hard problems of finding maximum-size subsets from given sets of k terminal pairs that can be routed via edge-disjoint paths (MaxEDP) or node-disjoint paths (MaxNDP) in a given graph. The approximability of MaxEDP/NDP is currently not well understood; the best known lower bound is Omega(log^{1/2 - varepsilon} n), assuming NP not subseteq ZPTIME(n^{poly log n}). This constitutes a significant gap to the best known approximation upper bound of O(n^1/2) due to Chekuri et al. (2006) and closing this gap is currently one of the big open problems in approximation algorithms. In their seminal paper, Raghavan and Thompson (Combinatorica, 1987) introduce the technique of randomized rounding for LPs; their technique gives an O(1)-approximation when edges (or nodes) may be used by O(log n/log log n) paths. In this paper, we strengthen the above fundamental results. We provide new bounds formulated in terms of the feedback vertex set number r of a graph, which measures its vertex deletion distance to a forest. In particular, we obtain the following. - For MaxEDP, we give an O(r^0.5 log^1.5 kr)-approximation algorithm. As r<=n, up to logarithmic factors, our result strengthens the best known ratio O(n^0.5) due to Chekuri et al. - Further, we show how to route Omega(opt) pairs with congestion O(log(kr)/log log(kr)), strengthening the bound obtained by the classic approach of Raghavan and Thompson. - For MaxNDP, we give an algorithm that gives the optimal answer in time (k+r)^O(r)n. This is a substantial improvement on the run time of 2^kr^O(r)n, which can be obtained via an algorithm by Scheffler. We complement these positive results by proving that MaxEDP is NP-hard even for r=1, and MaxNDP is W[1]-hard for parameter r. This shows that neither problem is fixed-parameter tractable in r unless FPT = W[1] and that our approximability results are relevant even for very small constant values of r.
Keywords
  • disjoint paths
  • approximation algorithms
  • feedback vertex set

Metrics

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

References

  1. Isolde Adler, Stavros G. Kolliopoulos, Philipp Klaus Krause, Daniel Lokshtanov, Saket Saurabh, and Dimitrios Thilikos. Tight bounds for linkages in planar graphs. In Proc. ICALP 2011, volume 6755 of Lecture Notes Comput. Sci., pages 110-121, 2011. Google Scholar
  2. Matthew Andrews. Approximation algorithms for the edge-disjoint paths problem via Räcke decompositions. In Proc. FOCS 2010, pages 277-286, 2010. Google Scholar
  3. Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, and Lisa Zhang. Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs. Combinatorica, 30(5):485-520, 2010. Google Scholar
  4. Yonatan Aumann and Yuval Rabani. Improved bounds for all optical routing. In Proc. SODA 1995, pages 567-576, 1995. Google Scholar
  5. Yonatan Aumann and Yuval Rabani. An O(log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput., 27(1):291-301, 1998. Google Scholar
  6. Baruch Awerbuch, Rainer Gawlick, Tom Leighton, and Yuval Rabani. On-line admission control and circuit routing for high performance computing and communication. In Proc. FOCS 1994, pages 412-423, 1994. Google Scholar
  7. Vineet Bafna, Piotr Berman, and Toshihiro Fujito. A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discrete Math., 12(3):289-297 (electronic), 1999. Google Scholar
  8. Hans L. Bodlaender, Stéphan Thomassé, and Anders Yeo. Kernel bounds for disjoint cycles and disjoint paths. Theoret. Comput. Sci., 412(35):4570-4578, 2011. URL: http://dx.doi.org/10.1016/j.tcs.2011.04.039.
  9. Andrei Z. Broder, Alan M. Frieze, Stephen Suen, and Eli Upfal. Optimal construction of edge-disjoint paths in random graphs. SIAM J. Comput., 28(2):541-573 (electronic), 1999. Google Scholar
  10. Andrei Z. Broder, Alan M. Frieze, and Eli Upfal. Existence and construction of edge-disjoint paths on expander graphs. SIAM J. Comput., 23(5):976-989, 1994. Google Scholar
  11. Chandra Chekuri and Alina Ene. Poly-logarithmic approximation for maximum node disjoint paths with constant congestion. In Proc. SODA 2013, pages 326-341, 2013. Google Scholar
  12. Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd. An O(√n) approximation and integrality gap for disjoint paths and unsplittable flow. Theory Comput., 2:137-146, 2006. URL: http://dx.doi.org/10.4086/toc.2006.v002a007.
  13. Chandra Chekuri, Sanjeev Khanna, and F Bruce Shepherd. A note on multiflows and treewidth. Algorithmica, 54(3):400-412, 2009. Google Scholar
  14. Chandra Chekuri, Marcelo Mydlarz, and F. Bruce Shepherd. Multicommodity demand flow in a tree and packing integer programs. ACM Trans. Algorithms, 3(3):Art. 27, 23, 2007. Google Scholar
  15. Chandra Chekuri, Guyslain Naves, and F. Bruce Shepherd. Maximum edge-disjoint paths in k-sums of graphs. In Proc. ICALP 2013, volume 7965 of Lecture Notes Comput. Sci., pages 328-339, 2013. Google Scholar
  16. Chandra Chekuri, Guyslain Naves, and F. Bruce Shepherd. Maximum edge-disjoint paths in k-sums of graphs, 2013. URL: http://arxiv.org/abs/1303.4897.
  17. Chandra Chekuri, F. Bruce Shepherd, and Christophe Weibel. Flow-cut gaps for integer and fractional multiflows. J. Comb. Theory, Ser. B, 103(2):248-273, 2013. Google Scholar
  18. Julia Chuzhoy. Routing in undirected graphs with constant congestion. In Proc. STOC 2012, pages 855-874, 2012. Google Scholar
  19. Julia Chuzhoy, David H. K. Kim, and Shi Li. Improved approximation for node-disjoint paths in planar graphs. In Proc. STOC 2016, 2016. to appear. Google Scholar
  20. Julia Chuzhoy and Shi Li. A polylogarithmic approximation algorithm for edge-disjoint paths with congestion 2. In Proc. FOCS 2012, pages 233-242, 2012. Google Scholar
  21. Alina Ene, Matthias Mnich, Marcin Pilipczuk, and Andrej Risteski. On routing disjoint paths in bounded treewidth graphs. In Proc. SWAT 2016, LIPIcs, 2016. to appear. Google Scholar
  22. Krzysztof Fleszar, Matthias Mnich, and Joachim Spoerhase. New algorithms for maximum disjoint paths based on tree-likeness, 2016. URL: http://arxiv.org/abs/1603.01740.
  23. Alan M. Frieze. Edge-disjoint paths in expander graphs. SIAM J. Comput., 30(6):1790-1801 (electronic), 2001. Google Scholar
  24. Naveen Garg, Vijay V. Vazirani, and Mihalis Yannakakis. Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica, 18(1):3-20, 1997. URL: http://dx.doi.org/10.1007/BF02523685.
  25. Oktay Günlük. A new min-cut max-flow ratio for multicommodity flows. SIAM J. Discrete Math., 21(1):1-15, 2007. Google Scholar
  26. Ian Holyer. The NP-completeness of edge-coloring. SIAM J. Comput., 10(4):718-720, 1981. Google Scholar
  27. Richard M. Karp. On the computational complexity of combinatorial problems. Networks, 5:45-68, 1975. Google Scholar
  28. Ken-ichi Kawarabayashi and Yusuke Kobayashi. Breaking O(n^1/2)-approximation algorithms for the edge-disjoint paths problem with congestion two. In Proc. STOC 2011, pages 81-88, 2011. Google Scholar
  29. Ken-ichi Kawarabayashi and Paul Wollan. A shorter proof of the graph minor algorithm: the unique linkage theorem. In Proc. STOC 2010, pages 687-694, 2010. Google Scholar
  30. Jon Kleinberg and Ronitt Rubinfeld. Short paths in expander graphs. In Proc. FOCS 1996, pages 86-95, 1996. Google Scholar
  31. Jon Kleinberg and Éva Tardos. Disjoint paths in densely embedded graphs. In Proc. FOCS 1995, pages 52-61, 1995. Google Scholar
  32. Jon Kleinberg and Éva Tardos. Approximations for the disjoint paths problem in high-diameter planar networks. J. Comput. System Sci., 57(1):61-73, 1998. Google Scholar
  33. Stavros G. Kolliopoulos and Clifford Stein. Approximating disjoint-path problems using packing integer programs. Math. Program., 99(1):63-87, 2004. Google Scholar
  34. Tom Leighton and Satish Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM, 46(6):787-832, 1999. Google Scholar
  35. Nathan Linial, Eran London, and Yuri Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215-245, 1995. Google Scholar
  36. Daniel Lokshtanov, M. S. Ramanujan, and Saket Saurabh. Linear time parameterized algorithms for subset feedback vertex set. In Proc. ICALP 2015, pages 935-946, 2015. Google Scholar
  37. Takao Nishizeki, Jens Vygen, and Xiao Zhou. The edge-disjoint paths problem is NP-complete for series-parallel graphs. Discrete Appl. Math., 115(1-3):177-186, 2001. URL: http://dx.doi.org/10.1016/S0166-218X(01)00223-2.
  38. Prabhakar Raghavan and Clark D. Tompson. Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica, 7(4):365-374, 1987. Google Scholar
  39. Satish Rao and Shuheng Zhou. Edge disjoint paths in moderately connected graphs. SIAM J. Comput., 39(5):1856-1887, 2010. Google Scholar
  40. Neil Robertson and P. D. Seymour. Graph minors. XIII. The disjoint paths problem. J. Combin. Theory Ser. B, 63(1):65-110, 1995. URL: http://dx.doi.org/10.1006/jctb.1995.1006.
  41. Petra Scheffler. A practical linear time algorithm for disjoint paths in graphs with bounded tree-width. Technical Report TR 396/1994, FU Berlin, Fachbereich 3 Mathematik, 1994. Google Scholar
  42. Loïc Séguin-Charbonneau and F. Bruce Shepherd. Maximum edge-disjoint paths in planar graphs with congestion 2. In Proc. FOCS 2011, pages 200-209, 2011. 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