Document Open Access Logo

Min-Cost Flow in Unit-Capacity Planar Graphs

Authors Adam Karczmarz , Piotr Sankowski

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.66.pdf
  • Filesize: 0.55 MB
  • 17 pages

Document Identifiers

Author Details

Adam Karczmarz
  • Institute of Informatics, University of Warsaw, Poland
Piotr Sankowski
  • Institute of Informatics, University of Warsaw, Poland

Funding

  • Karczmarz, Adam: Supported by ERC Consolidator Grant 772346 TUgbOAT and the Polish National Science Centre 2018/29/N/ST6/00757 grant.
  • Sankowski, Piotr: Supported by ERC Consolidator Grant 772346 TUgbOAT.

Cite As Get BibTex

Adam Karczmarz and Piotr Sankowski. Min-Cost Flow in Unit-Capacity Planar Graphs. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 66:1-66:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ESA.2019.66

Abstract

In this paper we give an O~((nm)^(2/3) log C) time algorithm for computing min-cost flow (or min-cost circulation) in unit capacity planar multigraphs where edge costs are integers bounded by C. For planar multigraphs, this improves upon the best known algorithms for general graphs: the O~(m^(10/7) log C) time algorithm of Cohen et al. [SODA 2017], the O(m^(3/2) log(nC)) time algorithm of Gabow and Tarjan [SIAM J. Comput. 1989] and the O~(sqrt(n) m log C) time algorithm of Lee and Sidford [FOCS 2014]. In particular, our result constitutes the first known fully combinatorial algorithm that breaks the Omega(m^(3/2)) time barrier for min-cost flow problem in planar graphs.
To obtain our result we first give a very simple successive shortest paths based scaling algorithm for unit-capacity min-cost flow problem that does not explicitly operate on dual variables. This algorithm also runs in O~(m^(3/2) log C) time for general graphs, and, to the best of our knowledge, it has not been described before. We subsequently show how to implement this algorithm faster on planar graphs using well-established tools: r-divisions and efficient algorithms for computing (shortest) paths in so-called dense distance graphs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Network flows
Keywords
  • minimum-cost flow
  • minimum-cost circulation
  • planar graphs

Metrics

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

Related Versions

References

  1. Mudabir Kabir Asathulla, Sanjeev Khanna, Nathaniel Lahn, and Sharath Raghvendra. A Faster Algorithm for Minimum-Cost Bipartite Perfect Matching in Planar Graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 457-476, 2018. URL: http://dx.doi.org/10.1137/1.9781611975031.31.
  2. Dimitri P. Bertsekas and Paul Tseng. Relaxation Methods for Minimum Cost Ordinary and Generalized Network Flow Problems. Operations Research, 36(1):93-114, 1988. URL: http://dx.doi.org/10.1287/opre.36.1.93.
  3. Glencora Borradaile and Philip N. Klein. An O(n log n) algorithm for maximum st-flow in a directed planar graph. J. ACM, 56(2):9:1-9:30, 2009. URL: http://dx.doi.org/10.1145/1502793.1502798.
  4. Glencora Borradaile, Philip N. Klein, Shay Mozes, Yahav Nussbaum, and Christian Wulff-Nilsen. Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time. SIAM J. Comput., 46(4):1280-1303, 2017. URL: http://dx.doi.org/10.1137/15M1042929.
  5. Robert G Busacker and Paul J Gowen. A procedure for determining a family of minimum-cost network flow patterns. Technical report, RESEARCH ANALYSIS CORP MCLEAN VA, 1960. Google Scholar
  6. Sergio Cabello, Erin W. Chambers, and Jeff Erickson. Multiple-Source Shortest Paths in Embedded Graphs. SIAM J. Comput., 42(4):1542-1571, 2013. URL: http://dx.doi.org/10.1137/120864271.
  7. Michael B. Cohen, Aleksander Madry, Piotr Sankowski, and Adrian Vladu. Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in Õ (m^10/7 log W) Time (Extended Abstract). In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 752-771, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.48.
  8. Samuel I. Daitch and Daniel A. Spielman. Faster approximate lossy generalized flow via interior point algorithms. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 451-460, 2008. URL: http://dx.doi.org/10.1145/1374376.1374441.
  9. Robert B. Dial. Algorithm 360: shortest-path forest with topological ordering [H]. Commun. ACM, 12(11):632-633, 1969. URL: http://dx.doi.org/10.1145/363269.363610.
  10. Jack Edmonds and Richard M. Karp. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. J. ACM, 19(2):248-264, 1972. URL: http://dx.doi.org/10.1145/321694.321699.
  11. Jeff Erickson. Maximum Flows and Parametric Shortest Paths in Planar Graphs. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 794-804, 2010. URL: http://dx.doi.org/10.1137/1.9781611973075.65.
  12. Shimon Even and Robert Endre Tarjan. Network Flow and Testing Graph Connectivity. SIAM J. Comput., 4(4):507-518, 1975. URL: http://dx.doi.org/10.1137/0204043.
  13. Jittat Fakcharoenphol and Satish Rao. Planar graphs, negative weight edges, shortest paths, and near linear time. J. Comput. Syst. Sci., 72(5):868-889, 2006. URL: http://dx.doi.org/10.1016/j.jcss.2005.05.007.
  14. L. R. Ford and D. R. Fulkerson. Constructing Maximal Dynamic Flows from Static Flows. Operations Research, 6(3):419-433, 1958. Google Scholar
  15. Harold N. Gabow and Robert Endre Tarjan. Faster Scaling Algorithms for Network Problems. SIAM J. Comput., 18(5):1013-1036, 1989. URL: http://dx.doi.org/10.1137/0218069.
  16. Pawel Gawrychowski and Adam Karczmarz. Improved Bounds for Shortest Paths in Dense Distance Graphs. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pages 61:1-61:15, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2018.61.
  17. Andrew V. Goldberg, Sagi Hed, Haim Kaplan, and Robert E. Tarjan. Minimum-Cost Flows in Unit-Capacity Networks. Theory Comput. Syst., 61(4):987-1010, 2017. URL: http://dx.doi.org/10.1007/s00224-017-9776-7.
  18. Andrew V. Goldberg and Robert E. Tarjan. Finding Minimum-Cost Circulations by Successive Approximation. Math. Oper. Res., 15(3):430-466, 1990. URL: http://dx.doi.org/10.1287/moor.15.3.430.
  19. John E. Hopcroft and Richard M. Karp. An n^5/2 Algorithm for Maximum Matchings in Bipartite Graphs. SIAM J. Comput., 2(4):225-231, 1973. URL: http://dx.doi.org/10.1137/0202019.
  20. Masao Iri. A new method of solving transportation-network problems. Journal of the Operations Research Society of Japan, 1960. Google Scholar
  21. Giuseppe F. Italiano, Adam Karczmarz, Jakub Łącki, and Piotr Sankowski. Decremental single-source reachability in planar digraphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 1108-1121, 2017. URL: http://dx.doi.org/10.1145/3055399.3055480.
  22. Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen. Improved algorithms for min cut and max flow in undirected planar graphs. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 313-322, 2011. URL: http://dx.doi.org/10.1145/1993636.1993679.
  23. William S. Jewell. Optimal Flow through Networks with Gains. Operations Research, 10(4):476-499, 1962. URL: http://www.jstor.org/stable/168050.
  24. Adam Karczmarz. Decremental Transitive Closure and Shortest Paths for Planar Digraphs and Beyond. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 73-92, 2018. URL: http://dx.doi.org/10.1137/1.9781611975031.5.
  25. Philip N. Klein. Multiple-source shortest paths in planar graphs. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005, pages 146-155, 2005. URL: http://dl.acm.org/citation.cfm?id=1070432.1070454.
  26. Philip N. Klein, Shay Mozes, and Christian Sommer. Structured recursive separator decompositions for planar graphs in linear time. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 505-514, 2013. URL: http://dx.doi.org/10.1145/2488608.2488672.
  27. Nathaniel Lahn and Sharath Raghvendra. A Faster Algorithm for Minimum-Cost Bipartite Matching in Minor-Free Graphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 569-588, 2019. URL: http://dx.doi.org/10.1137/1.9781611975482.36.
  28. Yin Tat Lee and Aaron Sidford. Path Finding Methods for Linear Programming: Solving Linear Programs in Õ(vrank) Iterations and Faster Algorithms for Maximum Flow. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 424-433, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.52.
  29. Gary L. Miller and Joseph Naor. Flow in Planar Graphs with Multiple Sources and Sinks. SIAM J. Comput., 24(5):1002-1017, 1995. URL: http://dx.doi.org/10.1137/S0097539789162997.
  30. Yahav Nussbaum. Network flow problems in planar graphs. PhD thesis, Tel Aviv University, 2014. Google Scholar
  31. James B. Orlin. A Faster Strongly Polynominal Minimum Cost Flow Algorithm. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA, pages 377-387, 1988. URL: http://dx.doi.org/10.1145/62212.62249.
  32. Thomas L Saaty and Robert G Busacker. Finite graphs and networks: An introduction with applications. McGraw-Hill Book Company, 1965. Google Scholar
  33. Piotr Sankowski. NC algorithms for weighted planar perfect matching and related problems. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pages 97:1-97:16, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2018.97.
  34. Éva Tardos. A strongly polynomial minimum cost circulation algorithm. Combinatorica, 5(3):247-256, 1985. URL: http://dx.doi.org/10.1007/BF02579369.
  35. Nobuaki Tomizawa. On some techniques useful for solution of transportation network problems. Networks, 1(2):173-194, 1971. 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 About DROPS Imprint Privacy Contact