Document Open Access Logo

Two-Commodity Flow Is Equivalent to Linear Programming Under Nearly-Linear Time Reductions

Authors Ming Ding, Rasmus Kyng, Peng Zhang

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.54.pdf
  • Filesize: 1.02 MB
  • 19 pages

Document Identifiers

Author Details

Ming Ding
  • ETH Zürich, Switzerland
Rasmus Kyng
  • ETH Zürich, Switzerland
Peng Zhang
  • Rutgers University, Piscataway, NJ, USA

Funding

  • Kyng, Rasmus: The research leading to these results has received funding from grant no. 200021 204787 of the Swiss National Science Foundation.

Cite AsGet BibTex

Ming Ding, Rasmus Kyng, and Peng Zhang. Two-Commodity Flow Is Equivalent to Linear Programming Under Nearly-Linear Time Reductions. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 54:1-54:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.54

Abstract

We give a nearly-linear time reduction that encodes any linear program as a 2-commodity flow problem with only a small blow-up in size. Under mild assumptions similar to those employed by modern fast solvers for linear programs, our reduction causes only a polylogarithmic multiplicative increase in the size of the program, and runs in nearly-linear time. Our reduction applies to high-accuracy approximation algorithms and exact algorithms. Given an approximate solution to the 2-commodity flow problem, we can extract a solution to the linear program in linear time with only a polynomial factor increase in the error. This implies that any algorithm that solves the 2-commodity flow problem can solve linear programs in essentially the same time. Given a directed graph with edge capacities and two source-sink pairs, the goal of the 2-commodity flow problem is to maximize the sum of the flows routed between the two source-sink pairs subject to edge capacities and flow conservation. A 2-commodity flow problem can be formulated as a linear program, which can be solved to high accuracy in almost the current matrix multiplication time (Cohen-Lee-Song JACM'21). Our reduction shows that linear programs can be approximately solved, to high accuracy, using 2-commodity flow as well. Our proof follows the outline of Itai’s polynomial-time reduction of a linear program to a 2-commodity flow problem (JACM’78). Itai’s reduction shows that exactly solving 2-commodity flow and exactly solving linear programming are polynomial-time equivalent. We improve Itai’s reduction to nearly preserve the problem representation size in each step. In addition, we establish an error bound for approximately solving each intermediate problem in the reduction, and show that the accumulated error is polynomially bounded. We remark that our reduction does not run in strongly polynomial time and that it is open whether 2-commodity flow and linear programming are equivalent in strongly polynomial time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Linear programming
Keywords
  • Two-Commodity Flow Problems
  • Linear Programming
  • Fine-Grained Complexity

Metrics

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

Related Versions

References

  1. Cynthia Barnhart, Niranjan Krishnan, and Pamela H. Vance. Multicommodity flow problems. In Christodoulos A. Floudas and Panos M. Pardalos, editors, Encyclopedia of Optimization, pages 2354-2362. Springer US, Boston, MA, 2009. URL: https://doi.org/10.1007/978-0-387-74759-0_407.
  2. L. Chen, G. Goranci, M. Henzinger, R. Peng, and T. Saranurak. Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1135-1146, November 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00109.
  3. Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, and Shang-Hua Teng. Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, pages 273-282, 2011. Google Scholar
  4. Michael B. Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. Journal of the ACM (JACM), 68(1):1-39, 2021. Google Scholar
  5. James Demmel, Ioana Dumitriu, and Olga Holtz. Fast linear algebra is stable. Numerische Mathematik, 108(1):59-91, 2007. Google Scholar
  6. Ming Ding, Rasmus Kyng, and Peng Zhang. Two-commodity flow is equivalent to linear programming under nearly-linear time reductions. arXiv preprint, 2022. URL: http://arxiv.org/abs/2201.11587.
  7. Efim A. Dinic. Algorithm for solution of a problem of maximum flow in networks with power estimation. In Soviet Math. Doklady, volume 11, pages 1277-1280, 1970. Google Scholar
  8. James R. Evans. A combinatorial equivalence between A class of multicommodity flow problems and the capacitated transportation problem. Mathematical Programming, 10(1):401-404, December 1976. URL: https://doi.org/10.1007/BF01580684.
  9. James R. Evans. The simplex method for integral multicommodity networks. Naval Research Logistics Quarterly, 25(1):31-37, March 1978. URL: https://doi.org/10.1002/nav.3800250104.
  10. Shimon Even and R. Endre Tarjan. Network flow and testing graph connectivity. SIAM journal on computing, 4(4):507-518, 1975. Google Scholar
  11. Lisa K. Fleischer. Approximating Fractional Multicommodity Flow Independent of the Number of Commodities. SIAM Journal on Discrete Mathematics, 13(4):505-520, January 2000. URL: https://doi.org/10.1137/S0895480199355754.
  12. Lester Randolph Ford and Delbert R. Fulkerson. Maximal flow through a network. Canadian journal of Mathematics, 8:399-404, 1956. Google Scholar
  13. Yu Gao, Yang P. Liu, and Richard Peng. Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao. arXiv:2101.07233 [cs], January 2021. URL: http://arxiv.org/abs/2101.07233.
  14. Naveen Garg and Jochen Könemann. Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems. SIAM Journal on Computing, 37(2):630-652, January 2007. URL: https://doi.org/10.1137/S0097539704446232.
  15. Andrew V. Goldberg and Satish Rao. Beyond the flow decomposition barrier. Journal of the ACM, 45(5):783-797, September 1998. URL: https://doi.org/10.1145/290179.290181.
  16. T. C. Hu. Multi-Commodity Network Flows. Operations Research, 11(3):344-360, June 1963. URL: https://doi.org/10.1287/opre.11.3.344.
  17. Alon Itai. Two-commodity flow. Journal of the ACM (JACM), 25(4):596-611, 1978. Google Scholar
  18. Arun Jambulapati and Aaron Sidford. Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 540-559. SIAM, 2021. Google Scholar
  19. Narendra Karmarkar. A new polynomial-time algorithm for linear programming. In Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, pages 302-311, 1984. Google Scholar
  20. Tarun Kathuria, Yang P. Liu, and Aaron Sidford. Unit Capacity Maxflow in Almost O (m^(4/3)) Time. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 119-130. IEEE, 2020. Google Scholar
  21. Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford. An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 217-226. SIAM, 2014. Google Scholar
  22. Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, and Zeyuan Allen Zhu. A simple, combinatorial algorithm for solving SDD systems in nearly-linear time. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pages 911-920, 2013. Google Scholar
  23. Jeff L. Kennington. A Survey of Linear Cost Multicommodity Network Flows. Operations Research, 26(2):209-236, 1978. Google Scholar
  24. Leonid G. Khachiyan. Polynomial algorithms in linear programming. USSR Computational Mathematics and Mathematical Physics, 20(1):53-72, 1980. Google Scholar
  25. Ioannis Koutis, Gary L. Miller, and Richard Peng. Approaching Optimality for Solving SDD Linear Systems. In Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS '10, pages 235-244, USA, October 2010. IEEE Computer Society. URL: https://doi.org/10.1109/FOCS.2010.29.
  26. Ioannis Koutis, Gary L. Miller, and Richard Peng. A nearly-m log n time solver for sdd linear systems. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 590-598. IEEE, 2011. Google Scholar
  27. Rasmus Kyng, Richard Peng, Sushant Sachdeva, and Di Wang. Flows in almost linear time via adaptive preconditioning. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 902-913, 2019. Google Scholar
  28. Rasmus Kyng and Sushant Sachdeva. Approximate gaussian elimination for laplacians-fast, sparse, and simple. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 573-582. IEEE, 2016. Google Scholar
  29. Rasmus Kyng, Di Wang, and Peng Zhang. Packing LPs are hard to solve accurately, assuming linear equations are hard. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 279-296. SIAM, 2020. Google Scholar
  30. Rasmus Kyng and Peng Zhang. Hardness results for structured linear systems. SIAM Journal on Computing, 49(4):FOCS17-280, 2020. Google Scholar
  31. Yin Tat Lee, Satish Rao, and Nikhil Srivastava. A new approach to computing maximum flows using electrical flows. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pages 755-764, 2013. Google Scholar
  32. Yin Tat Lee and Aaron Sidford. Path finding methods for linear programming: Solving linear programs in o (vrank) iterations and faster algorithms for maximum flow. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 424-433. IEEE, 2014. Google Scholar
  33. T. Leighton, F. Makedon, S. Plotkin, C. Stein, E. Tardos, and S. Tragoudas. Fast Approximation Algorithms for Multicommodity Flow Problems. Journal of Computer and System Sciences, 50(2):228-243, April 1995. URL: https://doi.org/10.1006/jcss.1995.1020.
  34. Yang P. Liu and Aaron Sidford. Faster energy maximization for faster maximum flow. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 803-814, 2020. Google Scholar
  35. Aleksander Madry. Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms. In Proceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC '10, pages 121-130, New York, NY, USA, June 2010. Association for Computing Machinery. URL: https://doi.org/10.1145/1806689.1806708.
  36. Aleksander Madry. Navigating central path with electrical flows: From flows to matchings, and back. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 253-262. IEEE, 2013. Google Scholar
  37. Aleksander Madry. Computing maximum flow with augmenting electrical flows. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 593-602. IEEE, 2016. Google Scholar
  38. Thomas Magnanti, R Ahuja, and J Orlin. Network flows: theory, algorithms, and applications. PrenticeHall, Upper Saddle River, NJ, 1993. Google Scholar
  39. Cameron Musco, Praneeth Netrapalli, Aaron Sidford, Shashanka Ubaru, and David P. Woodruff. Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness. arXiv:1704.04163 [cs, math], January 2019. URL: http://arxiv.org/abs/1704.04163.
  40. A. Ouorou, P. Mahey, and J.-Ph. Vial. A Survey of Algorithms for Convex Multicommodity Flow Problems. Management Science, 46(1):126-147, 2000. Google Scholar
  41. Richard Peng. Approximate undirected maximum flows in o (m polylog (n)) time. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1862-1867. SIAM, 2016. Google Scholar
  42. Richard Peng and Daniel A. Spielman. An efficient parallel solver for SDD linear systems. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, pages 333-342, 2014. Google Scholar
  43. James Renegar. A polynomial-time algorithm, based on Newton’s method, for linear programming. Mathematical programming, 40(1):59-93, 1988. Google Scholar
  44. James Renegar. Incorporating Condition Measures into the Complexity Theory of Linear Programming. SIAM Journal on Optimization, 5(3):506-524, August 1995. URL: https://doi.org/10.1137/0805026.
  45. Jonah Sherman. Nearly Maximum Flows in Nearly Linear Time. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 263-269, October 2013. URL: https://doi.org/10.1109/FOCS.2013.36.
  46. Jonah Sherman. Area-convexity, l∞ regularization, and undirected multicommodity flow. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 452-460, 2017. Google Scholar
  47. Daniel A. Spielman and Shang-Hua Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, STOC '04, pages 81-90, New York, NY, USA, June 2004. Association for Computing Machinery. URL: https://doi.org/10.1145/1007352.1007372.
  48. Pravin M. Vaidya. Speeding-up linear programming using fast matrix multiplication. In 30th Annual Symposium on Foundations of Computer Science, pages 332-337. IEEE Computer Society, 1989. Google Scholar
  49. Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Minimum cost flows, MDPs, and L1-regression in nearly linear time for dense instances. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, pages 859-869, New York, NY, USA, June 2021. Association for Computing Machinery. URL: https://doi.org/10.1145/3406325.3451108.
  50. I.-Lin Wang. Multicommodity network flows: A survey, Part I: Applications and Formulations. International Journal of Operations Research, 15(4):145-153, 2018. Google Scholar
  51. Virginia Vassilevska Williams and R. Ryan Williams. Subcubic Equivalences Between Path, Matrix, and Triangle Problems. Journal of the ACM, 65(5):27:1-27:38, August 2018. URL: https://doi.org/10.1145/3186893.
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