[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators

  • Full Length Paper
  • Series B
  • Published:
Mathematical Programming Submit manuscript

Abstract

Since 1997 there has been a steady stream of advances for the maximum disjoint paths problem. Achieving tractable results has usually required focusing on relaxations such as: (i) to allow some bounded edge congestion in solutions, (ii) to only consider the unit weight (cardinality) setting, (iii) to only require fractional routability of the selected demands (the all-or-nothing flow setting). For the general form (no congestion, general weights, integral routing) of edge-disjoint paths (edp) even the case of unit capacity trees which are stars generalizes the maximum matching problem for which Edmonds provided an exact algorithm. For general capacitated trees, Garg, Vazirani, Yannakakis showed the problem is APX-Hard and Chekuri, Mydlarz, Shepherd provided a 4-approximation. This is essentially the only setting where a constant approximation is known for the general form of edp. We extend their result by giving a constant-factor approximation algorithm for general-form edp in outerplanar graphs. A key component for the algorithm is to find a single-tree O(1) cut approximator for outerplanar graphs. Previously O(1) cut approximators were only known via distributions on trees and these were based implicitly on the results of Gupta, Newman, Rabinovich and Sinclair for distance tree embeddings combined with results of Anderson and Feige.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Notes

  1. A fundamental cut is one induced by a connected component after removing an edge in T.

References

  1. Abraham, I., Bartal, Y., Neiman, O.: Nearly tight low stretch spanning trees. In: FOCS, pp. 781–790 (2008)

  2. Alon, N., Karp, R.M., Peleg, D., West, D.: A graph-theoretic game and its application to the k-server problem. SIAM J. Comput. 24(1), 78–100 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  3. Andersen, R., Feige, U.: Interchanging distance and capacity in probabilistic mappings. arXiv preprint arXiv:0907.3631 (2009)

  4. Chekuri, C., Khanna, S., Shepherd, F.B.: Edge-disjoint paths in planar graphs with constant congestion. SIAM J. Comput. 39, 281–301 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  5. Chekuri, C., Ene, A.: Poly-logarithmic approximation for maximum node disjoint paths with constant congestion. In: Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pp. 326–341. SIAM (2013)

  6. Chekuri, C., Khanna, S., Shepherd, F.B.: The all-or-nothing multicommodity flow problem. In: STOC ’04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pp. 156–165, New York, NY, USA (2004). ACM

  7. Chekuri, C., Khanna, S., Shepherd, F.B.: The all-or-nothing multicommodity flow problem. SIAM J. Comput. 42(4), 1467–1493 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  8. Chekuri, C., Mydlarz, M., Shepherd, F.B.: Multicommodity demand flow in a tree and packing integer programs. ACM Trans. Algorithms (TALG) 3(3), 27 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  9. Chekuri, C., Naves, G., Shepherd, F.B.: Maximum edge-disjoint paths in k-sums of graphs. In: International Colloquium on Automata, Languages, and Programming, pp. 328–339. Springer (2013)

  10. Chuzhoy, J., Li, S.: A polylogarithimic approximation algorithm for edge-disjoint paths with congestion 2. arXiv preprint arXiv:1208.1272 (2012)

  11. Chuzhoy, J., Li, S.: A polylogarithimic approximation algorithm for edge-disjoint paths with congestion 2. In: Proceedings of IEEE FOCS (2012)

  12. Chuzhoy, J., Kim, D.H.K., Nimavat, R.: New hardness results for routing on disjoint paths. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 86–99 (2017)

  13. Elkin, M., Emek, Y., Spielman, D.A., Teng, S.-H.: Lower-stretch spanning trees. SIAM J. Comput. 38(2), 608–628 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  14. Englert, M., Gupta, A., Krauthgamer, R., Racke, H., Talgam-Cohen, I., Talwar, K.: Vertex sparsifiers: new results from old techniques. SIAM J. Comput. 43(4), 1239–1262 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  15. Frank, A.: Edge-disjoint paths in planar graphs. J. Comb. Theory Ser. B 39(2), 164–178 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  16. Garg, N., Kumar, N., Sebő, A.: Integer plane multiflow maximisation: flow-cut gap and one-quarter-approximation. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 144–157. Springer (2020)

  17. Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18(1), 3–20 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  18. Gupta, A., Newman, I., Rabinovich, Y., Sinclair, A.: Cuts, trees and \(\ell _1\)-embeddings of graphs. Combinatorica 24(2), 233–269 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  19. Gupta, A.: Steiner points in tree metrics don’t (really) help. SODA 1, 220–227 (2001)

    MathSciNet  MATH  Google Scholar 

  20. Guruswami, V., Khanna, S., Rajaraman, R., Shepherd, B., Yannakakis, M.: Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. J. Comput. Syst. Sci. 67(3), 473–496 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  21. Harrelson, C., Hildrum, K., Rao, S.: A polynomial-time tree decomposition to minimize congestion. In: Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, pp. 34–43 (2003)

  22. Huang, C.-C., Mari, M., Mathieu, C., Schewior, K., Vygen, J.: An approximation algorithm for fully planar edge-disjoint paths. arXiv preprint arXiv:2001.01715 (2020)

  23. Kawarabayashi, K., Kobayashi, Y.: All-or-nothing multicommodity flow problem with bounded fractionality in planar graphs. SIAM J. Comput. 47(4), 1483–1504 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  24. Kleinberg, J., Tardos, E.: Approximations for the disjoint paths problem in high-diameter planar networks. J. Comput. Syst. Sci. 57(1), 61–73 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  25. Okamura, H., Seymour, P.D.: Multicommodity flows in planar graphs. J. Combin. Theory Ser. B 31(1), 75–81 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  26. Rabinovich, Y., Raz, R.: Lower bounds on the distortion of embedding finite metric spaces in graphs. Discrete Comput. Geom. 19(1), 79–94 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  27. Räcke, H.: Minimizing congestion in general networks. In: Proceedings of IEEE FOCS, pp. 43–52 (2002)

  28. Räcke, H.: Optimal hierarchical decompositions for congestion minimization in networks. In: STOC, pp. 255–264 (2008)

  29. Räcke, H., Shah, C.: Improved guarantees for tree cut sparsifiers. In: European Symposium on Algorithms, pp. 774–785. Springer (2014)

  30. Seguin-Charbonneau, L., Shepherd, F.B.: Maximum edge-disjoint paths in planar graphs with congestion. Math. Program. 1, 29 (2020)

    MATH  Google Scholar 

  31. Seymour, P.D.: Matroids and multicommodity flows. Eur. J. Combin. 2(3), 257–290 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  32. Sidiropoulos, A.: Private communication (2014)

Download references

Author information

Authors and Affiliations

  1. LIS, CNRS UMR 7020, Aix-Marseille University, Marseille, France

    Guyslain Naves

  2. University of British Columbia, Vancouver, BC, Canada

    F. Bruce Shepherd & Henry Xia

Authors
  1. Guyslain Naves
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. F. Bruce Shepherd
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Henry Xia
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to F. Bruce Shepherd.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Naves, G., Shepherd, F.B. & Xia, H. Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators. Math. Program. 197, 1049–1067 (2023). https://doi.org/10.1007/s10107-022-01780-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-022-01780-0

Mathematics Subject Classification

Search

Navigation