pith. sign in

arxiv: 1907.02274 · v1 · pith:GSVLJKFHnew · submitted 2019-07-04 · 💻 cs.DS

Min-Cost Flow in Unit-Capacity Planar Graphs

Adam Karczmarz , Piotr Sankowski This is my paper

Pith reviewed 2026-05-25 09:28 UTC · model grok-4.3

classification 💻 cs.DS
keywords min-cost flowplanar multigraphsunit capacityscaling algorithmr-divisionsdense distance graphssuccessive shortest pathscombinatorial algorithm
0
0 comments X

The pith

A scaling algorithm computes min-cost flow on unit-capacity planar multigraphs in Õ((nm)^{2/3} log C) time.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a faster algorithm for the min-cost flow problem restricted to planar multigraphs with unit capacities and integer edge costs up to C. It first introduces a simple successive shortest paths scaling method that achieves Õ(m^{3/2} log C) time on arbitrary graphs without using dual variables explicitly. The method is then accelerated on planar graphs by decomposing them with r-divisions and computing paths via oracles on dense distance graphs. If correct, the result improves all prior general-graph bounds when applied to planar instances and supplies the first fully combinatorial planar algorithm to run faster than Õ(m^{3/2}). A reader would care because min-cost flow appears in many network design and routing tasks where planarity is natural.

Core claim

We give an Õ((nm)^{2/3} log C) time algorithm for computing min-cost flow or min-cost circulation in unit-capacity planar multigraphs with integer costs bounded by C. This is obtained from a new successive shortest paths based scaling algorithm that also runs in Õ(m^{3/2} log C) time on general graphs, followed by an implementation that exploits r-divisions and efficient shortest-path algorithms on dense distance graphs to obtain the improved planar bound. The algorithm is fully combinatorial and improves upon the Õ(m^{10/7} log C), O(m^{3/2} log(nC)), and Õ(√n m log C) bounds of prior work when specialized to planar graphs.

What carries the argument

Successive shortest paths scaling algorithm accelerated on planar graphs using r-divisions and shortest-path oracles on dense distance graphs.

If this is right

  • The same scaling procedure yields an Õ(m^{3/2} log C) algorithm for min-cost flow on general unit-capacity graphs.
  • The planar result is the first fully combinatorial algorithm to break the Õ(m^{3/2}) barrier for this problem.
  • The algorithm applies equally to min-cost circulation.
  • It improves the running times of the Cohen et al., Gabow-Tarjan, and Lee-Sidford algorithms on planar instances.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The combination of scaling with r-divisions may extend to capacitated or approximate variants of planar flow problems.
  • Dense distance graph techniques could support dynamic updates or batched queries in planar networks.
  • Because the base algorithm avoids dual variables, it may translate more readily into practical code for map-based optimization tasks.

Load-bearing premise

That r-divisions and dense distance graph path computations can be plugged into the successive shortest paths scaling procedure while preserving both correctness and the claimed running-time improvement.

What would settle it

A concrete planar unit-capacity multigraph instance with small integer costs on which the algorithm either returns a flow whose cost exceeds the known optimum or exceeds the Õ((nm)^{2/3} log C) time bound by more than a logarithmic factor.

read the original abstract

In this paper we give an $\widetilde{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 $\widetilde{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 $\widetilde{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 $\widetilde{O}(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 $\widetilde{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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper claims an Õ((nm)^{2/3} log C) time algorithm for min-cost flow (or circulation) in unit-capacity planar multigraphs with integer costs bounded by C. It first presents a new successive-shortest-paths scaling algorithm for general unit-capacity graphs that runs in Õ(m^{3/2} log C) time and avoids explicit dual variables, then accelerates the algorithm on planar graphs via r-divisions and shortest-path computations in dense distance graphs.

Significance. If correct, the result improves on the Õ(m^{10/7} log C), O(m^{3/2} log(nC)), and Õ(√n m log C) bounds for general graphs and supplies the first fully combinatorial planar algorithm to break the Õ(m^{3/2}) barrier. The approach re-uses standard planar primitives (r-divisions, dense distance graphs) whose known bounds are stated to combine with the new scaling procedure to produce the (nm)^{2/3} exponent.

minor comments (2)
  1. [Abstract] Abstract: the claim that the general-graph scaling algorithm 'has not been described before' would be strengthened by a short explicit comparison (in the introduction or §2) to the scaling frameworks of Gabow-Tarjan and Cohen et al. to isolate the precise technical difference.
  2. [Abstract] Abstract, final paragraph: the high-level description of how r-divisions and dense-distance-graph shortest paths are combined with the scaling procedure should be expanded in the body with a parameter-setting argument that derives the precise (nm)^{2/3} exponent from the known running times of the cited primitives.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive review, recognition of the significance of our result, and recommendation of minor revision. The report accurately summarizes our contributions.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation introduces a new successive-shortest-paths scaling algorithm (claimed novel and Õ(m^{3/2} log C) on general unit-capacity graphs) whose planar speedup is obtained by composing it with externally published, independently established primitives (r-divisions and dense-distance-graph shortest paths). No equation reduces to a prior fitted parameter or self-citation by construction, no uniqueness theorem is imported from the authors' own prior work, and no ansatz is smuggled via self-citation. The central result is therefore a direct algorithmic combination whose correctness rests on the cited external bounds rather than on any internal redefinition or renaming of its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on standard graph-theoretic assumptions and prior planar-graph machinery; no new free parameters or invented entities appear in the abstract.

axioms (2)
  • domain assumption Input graphs are planar multigraphs with unit capacities and integer edge costs bounded by C
    Explicitly stated as the problem setting in the abstract.
  • domain assumption r-divisions and dense distance graphs permit efficient path computations that yield the claimed speedup on planar graphs
    Invoked in the final sentence of the abstract as the source of the planar improvement.

pith-pipeline@v0.9.0 · 5801 in / 1398 out tokens · 39423 ms · 2026-05-25T09:28:46.207559+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

40 extracted references · 40 canonical work pages

  1. [1]

    Klawe, Shlomo Moran, Peter W

    Alok Aggarwal, Maria M. Klawe, Shlomo Moran, Peter W. Sho r, and Robert E. Wilber. Geometric applications of a matrix-searching algorithm. Algorithmica, 2:195–208, 1987. doi:10.1007/BF01840359

    work page doi:10.1007/bf01840359 1987

  2. [2]

    A faster algorithm for minimum-cost bipartite perfect matching in p lanar graphs

    Mudabir Kabir Asathulla, Sanjeev Khanna, Nathaniel Lah n, and Sharath Raghvendra. A faster algorithm for minimum-cost bipartite perfect matching in p lanar graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algori thms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018 , pages 457–476, 2018. doi:10.1137/1.9781611975031.31

    work page doi:10.1137/1.9781611975031.31 2018

  3. [3]

    Bertsekas and Paul Tseng

    Dimitri P. Bertsekas and Paul Tseng. Relaxation methods for minimum cost ordinary and general- ized network flow problems.Operations Research, 36(1):93–114, 1988. doi:10.1287/opre.36.1.93

    work page doi:10.1287/opre.36.1.93 1988

  4. [4]

    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. doi:10.1145/1502793.1502798

    work page doi:10.1145/1502793.1502798 2009

  5. [5]

    Klein, Shay Mozes, Yahav Nussbaum, and Christian Wulff-Nilsen

    Glencora Borradaile, Philip N. Klein, Shay Mozes, Yahav Nussbaum, and Christian Wulff-Nilsen. Multiple-source multiple-sink maximum flow in directed pla nar graphs in near-linear time. SIAM J. Comput. , 46(4):1280–1303, 2017. doi:10.1137/15M1042929

    work page doi:10.1137/15m1042929 2017

  6. [6]

    A procedure for determ ining a family of minimum-cost network flow patterns

    Robert G Busacker and Paul J Gowen. A procedure for determ ining a family of minimum-cost network flow patterns. Technical report, RESEARCH ANALYSIS CORP MCLEAN V A, 1960

    work page 1960

  7. [7]

    Chambers, and Jeff Erickson

    Sergio Cabello, Erin W. Chambers, and Jeff Erickson. Mult iple-source shortest paths in embedded graphs. SIAM J. Comput. , 42(4):1542–1571, 2013. doi:10.1137/120864271

    work page doi:10.1137/120864271 2013

  8. [8]

    Cohen, Aleksander Madry, Piotr Sankowski, an d Adrian Vladu

    Michael B. Cohen, Aleksander Madry, Piotr Sankowski, an d Adrian Vladu. Negative-weight shortest paths and unit capacity minimum cost flow in ˜ o ( m10/7 log W ) time (extended ab- stract). In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposiu m on Discrete Algo- rithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, Janu ary 16-19 , pages 752–771, ...

    work page doi:10.1137/1.9781611974782.48 2017

  9. [9]

    Daitch and Daniel A

    Samuel I. Daitch and Daniel A. Spielman. Faster approxim ate lossy generalized flow via interior point algorithms. In Proceedings of the 40th Annual ACM Symposium on Theory of Com puting, Victoria, British Columbia, Canada, May 17-20, 2008 , pages 451–460, 2008. doi:10.1145/1374376.1374441

    work page doi:10.1145/1374376.1374441 2008

  10. [10]

    Robert B. Dial. Algorithm 360: shortest-path forest wi th topological ordering [H]. Commun. ACM, 12(11):632–633, 1969. doi:10.1145/363269.363610

    work page doi:10.1145/363269.363610 1969

  11. [11]

    Hybrid bellman-ford-dij kstra algorithm

    Yefim Dinitz and Rotem Itzhak. Hybrid bellman-ford-dij kstra algorithm. J. Discrete Algorithms , 42:35–44, 2017. doi:10.1016/j.jda.2017.01.001

    work page doi:10.1016/j.jda.2017.01.001 2017

  12. [12]

    Jack Edmonds and Richard M. Karp. Theoretical improvem ents in algorithmic efficiency for network flow problems.J. ACM , 19(2):248–264, 1972. doi:10.1145/321694.321699. 16

    work page doi:10.1145/321694.321699 1972

  13. [13]

    Maximum flows and parametric shortest paths in planar graphs

    Jeff Erickson. Maximum flows and parametric shortest paths in planar graphs. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algori thms, SODA 2010, Austin, Texas, USA, January 17-19, 2010 , pages 794–804, 2010. doi:10.1137/1.9781611973075.65

    work page doi:10.1137/1.9781611973075.65 2010

  14. [14]

    Network flow and tes ting graph connectivity

    Shimon Even and Robert Endre Tarjan. Network flow and tes ting graph connectivity. SIAM J. Comput., 4(4):507–518, 1975. doi:10.1137/0204043

    work page doi:10.1137/0204043 1975

  15. [15]

    Planar graphs, n egative weight edges, shortest paths, and near linear time

    Jittat Fakcharoenphol and Satish Rao. Planar graphs, n egative weight edges, shortest paths, and near linear time. J. Comput. Syst. Sci. , 72(5):868–889, 2006. doi:10.1016/j.jcss.2005.05.007

    work page doi:10.1016/j.jcss.2005.05.007 2006

  16. [16]

    L. R. Ford and D. R. Fulkerson. Constructing maximal dyn amic flows from static flows.Operations Research, 6(3):419–433, 1958

    work page 1958

  17. [17]

    Gabow and Robert Endre Tarjan

    Harold N. Gabow and Robert Endre Tarjan. Faster scaling algorithms for network problems. SIAM J. Comput. , 18(5):1013–1036, 1989. doi:10.1137/0218069

    work page doi:10.1137/0218069 1989

  18. [18]

    Improved bound s for shortest paths in dense distance graphs

    Pawel Gawrychowski and Adam Karczmarz. Improved bound s for shortest paths in dense distance graphs. In 45th International Colloquium on Automata, Languages, and Pro- gramming, ICALP 2018, July 9-13, 2018, Prague, Czech Republ ic, pages 61:1–61:15, 2018. doi:10.4230/LIPIcs.ICALP.2018.61

    work page doi:10.4230/lipics.icalp.2018.61 2018

  19. [19]

    Goldberg, Sagi Hed, Haim Kaplan, and Robert E

    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. doi:10.1007/s00224-017-9776-7

    work page doi:10.1007/s00224-017-9776-7 2017

  20. [20]

    Goldberg and Robert E

    Andrew V. Goldberg and Robert E. Tarjan. Finding minimu m-cost circulations by successive ap- proximation. Math. Oper. Res. , 15(3):430–466, 1990. doi:10.1287/moor.15.3.430

    work page doi:10.1287/moor.15.3.430 1990

  21. [21]

    Hopcroft and Richard M

    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. doi:10.1137/0202019

    work page doi:10.1137/0202019 1973

  22. [22]

    A new method of solving transportation-netw ork problems

    Masao Iri. A new method of solving transportation-netw ork problems. 1960

    work page 1960

  23. [23]

    Italiano, Adam Karczmarz, Jakub Łącki, and Piotr Sankowski

    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, Jun e 19-23, 2017 , pages 1108–1121,

    work page 2017

  24. [24]

    doi:10.1145/3055399.3055480

    work page doi:10.1145/3055399.3055480

  25. [25]

    Italiano, Yahav Nussbaum, Piotr Sankowski , and Christian Wulff-Nilsen

    Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski , and Christian Wulff-Nilsen. Improved algorithms for min cut and max flow in undirected planar graph s. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, US A, 6-8 June 2011 , pages 313–322, 2011. doi:10.1145/1993636.1993679

    work page doi:10.1145/1993636.1993679 2011

  26. [26]

    William S. Jewell. Optimal flow through networks with ga ins. Operations Research, 10(4):476–499,

    work page

  27. [27]

    URL: http://www.jstor.org/stable/168050

    work page

  28. [28]

    Decremental transitive closure and sh ortest paths for planar digraphs and beyond

    Adam Karczmarz. Decremental transitive closure and sh ortest paths for planar digraphs and beyond. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Al- gorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 201 8, pages 73–92, 2018. doi:10.1137/1.9781611975031.5

    work page doi:10.1137/1.9781611975031.5 2018

  29. [29]

    Philip N. Klein. Multiple-source shortest paths in pla nar graphs. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 200 5, Vancouver, British Columbia, Canada, January 23-25, 2005 , pages 146–155, 2005

    work page 2005

  30. [30]

    Klein, Shay Mozes, and Christian Sommer

    Philip N. Klein, Shay Mozes, and Christian Sommer. Stru ctured 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. doi:10.1145/2488608.2488672. 17

    work page doi:10.1145/2488608.2488672 2013

  31. [31]

    A faster algori thm for minimum-cost bipartite matching in minor-free graphs

    Nathaniel Lahn and Sharath Raghvendra. A faster algori thm for minimum-cost bipartite matching in minor-free graphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on D iscrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019 , pages 569–588, 2019. doi:10.1137/1.9781611975482.36

    work page doi:10.1137/1.9781611975482.36 2019

  32. [32]

    Path finding methods for li near programming: Solving linear programs in ˜ o(vrank) iterations and faster algorithms for maximum flow

    Yin Tat Lee and Aaron Sidford. Path finding methods for li near programming: Solving linear programs in ˜ o(vrank) iterations and faster algorithms for maximum flow. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Ph iladelphia, PA, USA, October 18-21, 2014 , pages 424–433, 2014. doi:10.1109/FOCS.2014.52

    work page doi:10.1109/focs.2014.52 2014

  33. [33]

    Miller and Joseph Naor

    Gary L. Miller and Joseph Naor. Flow in planar graphs wit h multiple sources and sinks. SIAM J. Comput., 24(5):1002–1017, 1995. doi:10.1137/S0097539789162997

    work page doi:10.1137/s0097539789162997 1995

  34. [34]

    Shortest paths i n planar graphs with real lengths in O (nlog2n/loglogn) time

    Shay Mozes and Christian Wulff-Nilsen. Shortest paths i n planar graphs with real lengths in O (nlog2n/loglogn) time. In Algorithms - ESA 2010, 18th Annual European Sym- posium, Liverpool, UK, September 6-8, 2010. Proceedings, P art II , pages 206–217, 2010. doi:10.1007/978-3-642-15781-3\_18

    work page doi:10.1007/978-3-642-15781-3 2010

  35. [35]

    Network flow problems in planar graphs

    Yahav Nussbaum. Network flow problems in planar graphs . PhD thesis, 2014

    work page 2014

  36. [36]

    James B. Orlin. A faster strongly polynominal minimum c ost flow algorithm. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 19 88, Chicago, Illinois, USA , pages 377–387, 1988. doi:10.1145/62212.62249

    work page doi:10.1145/62212.62249 1988

  37. [37]

    Finite graphs and networks: An introduction with appli- cations

    Thomas L Saaty and Robert G Busacker. Finite graphs and networks: An introduction with appli- cations. McGraw-Hill Book Company, 1965

    work page 1965

  38. [38]

    NC algorithms for weighted planar per fect matching and related problems

    Piotr Sankowski. NC algorithms for weighted planar per fect 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. doi:10.4230/LIPIcs.ICALP.2018.97

    work page doi:10.4230/lipics.icalp.2018.97 2018

  39. [39]

    A strongly polynomial minimum cost circulation algorithm

    ´Eva Tardos. A strongly polynomial minimum cost circulation algorithm. Combinatorica, 5(3):247– 256, 1985. doi:10.1007/BF02579369

    work page doi:10.1007/bf02579369 1985

  40. [40]

    On some techniques useful for soluti on of transportation network problems

    Nobuaki Tomizawa. On some techniques useful for soluti on of transportation network problems. Networks, 1(2):173–194, 1971. 18 A Reducing to the Case with an r-division with Few Holes Theorem A.1 ([28]). Let G be a simple triangulated connected plane graph with n vertices. For any r ∈ [1, n ], an r-division with few holes of G can be computed in O(n) time...

    work page 1971