Document Open Access Logo

Approximating Maximum Integral Multiflows on Bounded Genus Graphs

Authors Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Jens Vygen

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.80.pdf
  • Filesize: 0.88 MB
  • 18 pages

Document Identifiers

Author Details

Chien-Chung Huang
  • CNRS, ENS, PSL, Paris, France
Mathieu Mari
  • University of Warsaw, Poland
Claire Mathieu
  • CNRS, IRIF, Université de Paris, France
Jens Vygen
  • Research Institute for Discrete Mathematics & Hausdorff Center for Mathematics, University of Bonn, Germany

Acknowledgements

The authors would like to thank Arnaud de Mesmay for useful suggestions. This work was partially funded by the grant ANR-19-CE48-0016 from the French National Research Agency (ANR).

Cite AsGet BibTex

Chien-Chung Huang, Mathieu Mari, Claire Mathieu, and Jens Vygen. Approximating Maximum Integral Multiflows on Bounded Genus Graphs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 80:1-80:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.80

Abstract

We devise the first constant-factor approximation algorithm for finding an integral multi-commodity flow of maximum total value for instances where the supply graph together with the demand edges can be embedded on an orientable surface of bounded genus. This extends recent results for planar instances. Our techniques include an uncrossing algorithm, which is significantly more difficult than in the planar case, a partition of the cycles in the support of an LP solution into free homotopy classes, and a new rounding procedure for freely homotopic non-separating cycles.

Subject Classification

ACM Subject Classification
  • Theory of computation → Routing and network design problems
Keywords
  • Multi-commodity flows
  • approximation algorithms
  • bounded genus graphs

Metrics

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

Related Versions

References

  1. Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows. Prentice-Hall, 1993. Google Scholar
  2. Matthew Andrews, Julia Chuzhoy, Sanjeev Khanna, and Lisa Zhang. Hardness of the undirected edge-disjoint paths problem with congestion. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 226-244, 2015. Google Scholar
  3. Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, and D. Sivakumar. On the hardness of approximating multicut and sparsest-cut. Computational Complexity, 15(2):94-114, 2006. Google Scholar
  4. Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd. An O(√n) approximation and integrality gap for disjoint paths and unsplittable flow. Theory of Computing, 2:137-146, 2006. Google Scholar
  5. Chandra Chekuri, F. Bruce Shepherd, and Christophe Weibel. Flow-cut gaps for integer and fractional multiflows. Journal of Combinatorial Theory, Series B, 103(2):248-273, 2013. Google Scholar
  6. Julia Chuzhoy, David H. K. Kim, and Rachit Nimavat. New hardness results for routing on disjoint paths. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing Conference (STOC), pages 86-99, 2017. Google Scholar
  7. Julia Chuzhoy, David H. K. Kim, and Rachit Nimavat. Almost polynomial hardness of node-disjoint paths in grids. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing Conference (STOC), pages 1220-1233, 2018. Google Scholar
  8. Vincent Cohen-Addad, Éric Colin de Verdière, and Arnaud de Mesmay. A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1439-1458, 2018. Google Scholar
  9. Éric Colin de Verdière. Topological algorithms for graphs on surfaces. In J.E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry. CRC Press, 2017. Chapter 23. Google Scholar
  10. Marie-Christine Costa, Lucas Letocart, and Frederic Roupin. Minimal multicut and maximal integer multiflow: A survey. European Journal of Operational Research, 162(1):55-69, 2005. Google Scholar
  11. Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, and Mihalis Yannakakis. The complexity of multiterminal cuts. SIAM Journal on Computing, 23(4):864–894, 1994. Google Scholar
  12. David B. A. Epstein. Curves on 2-manifolds and isotopies. Acta Mathematica, 115:83-107, 1966. URL: https://doi.org/10.1007/BF02392203.
  13. Jeff Erickson and Kim Whittlesey. Transforming curves on surfaces redux. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1646-1655. SIAM, 2013. URL: https://doi.org/10.1137/1.9781611973105.118.
  14. Samuel Fiorini, Nadia Hardy, Bruce Reed, and Adrian Vetta. Approximate min–max relations for odd cycles in planar graphs. Mathematical Programming, 110(1):71-91, 2007. Google Scholar
  15. Lester R. Ford and Delbert R. Fulkerson. Flows in Networks. Princeton University Press, 1962. Google Scholar
  16. Naveen Garg, Nikhil Kumar, and András Sebő. Integer plane multiflow maximisation: Flow-cut gap and one-quarter-approximation. In Proceedings of IPCO, pages 144-157, 2020. Google Scholar
  17. Naveen Garg, Vijay Vazirani, and Mihalis Yannakakis. Approximate max-flow min-(multi)cut theorems and their applications. SIAM Journal on Computing, 25(2):235-251, April 1996. Google Scholar
  18. Naveen Garg, Vijay Vazirani, and Mihalis Yannakakis. Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica, 18(1):3-20, 1997. Google Scholar
  19. Joshua Evan Greene. On curves intersecting at most once, 2018. URL: http://arxiv.org/abs/1807.05658.
  20. Percy J. Heawood. Map colour theorem. Quarterly Journal of Mathematics, 24:332-338, 1890. Google Scholar
  21. Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Kevin Schewior, and Jens Vygen. An approximation algorithm for fully planar edge-disjoint paths. SIAM Journal on Discrete Mathematics, 35:752-769, 2021. Google Scholar
  22. Richard M. Karp. On the computational complexity of combinatorial problems. Networks, 5(1):45-68, 1975. Google Scholar
  23. Ken-ichi Kawarabayashi and Yusuke Kobayashi. An O(log n)-approximation algorithm for the edge-disjoint paths problem in Eulerian planar graphs. ACM Transactions on Algorithms, 9(2):16:1-16:13, 2013. Google Scholar
  24. Philip Klein, Serge A. Plotkin, and Satish Rao. Excluded minors, network decomposition, and multicommodity flow. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (STOC), pages 682-690, 1993. URL: https://doi.org/10.1145/167088.167261.
  25. Philip N. Klein, Claire Mathieu, and Hang Zhou. Correlation clustering and two-edge-connected augmentation for planar graphs. In Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science (STACS), pages 554-567, 2014. Google Scholar
  26. Francis Lazarus and Julien Rivaud. On the homotopy test on surfaces. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, (FOCS), pages 440-449. IEEE Computer Society, 2012. URL: https://doi.org/10.1109/FOCS.2012.12.
  27. Justin Malestein, Igor Rivin, and Louis Theran. Topological designs. Geometriae Dedicata, 168:221-233, August 2010. URL: https://doi.org/10.1007/s10711-012-9827-9.
  28. Matthias Middendorf and Frank Pfeiffer. On the complexity of the disjoint paths problem. Combinatorica, 13(1):97-107, March 1993. URL: https://doi.org/10.1007/BF01202792.
  29. Bojan Mohar and Carsten Thomassen. Graphs on Surfaces. Johns Hopkins Series in the Mathematical Sciences. Johns Hopkins University Press, 2001. URL: http://jhupbooks.press.jhu.edu/ecom/MasterServlet/GetItemDetailsHandler?iN=9780801866890&qty=1&source=2&viewMode=3&loggedIN=false&JavaScript=y.
  30. Guyslain Naves and András Sebő. Multiflow feasibility: an annotated tableau. In W. Cook, L. Lovász, and J. Vygen, editors, Research Trends in Combinatorial Optimization, pages 261-283. Springer, 2009. Google Scholar
  31. Piotr Przytycki. Arcs intersecting at most once. Geometric and Functional Analysis, 25:658-670, February 2015. URL: https://doi.org/10.1007/s00039-015-0320-0.
  32. Neil Robertson, Daniel P. Sanders, Paul Seymour, and Robin Thomas. Efficiently four-coloring planar graphs. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (SODA), pages 571-575, 1996. Google Scholar
  33. Neil Robertson and Paul D. Seymour. Graph minors. XIII. The disjoint paths problem. Journal of Combinatorial Theory, Series B, 63(1):65-110, 1995. Google Scholar
  34. Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer, 2003. Google Scholar
  35. András Sebö. Integer plane multiflows with a fixed number of demands. Journal of Combinatorial Theory, Series B, 59(2):163-171, 1993. URL: https://doi.org/10.1006/jctb.1993.1062.
  36. Éva Tardos and Vijay V. Vazirani. Improved bounds for the max-flow min-multicut ratio for planar and K_r,r-free graphs. Information Processing Letters, 47:77-80, August 1993. 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