Abstract
In this paper we give an O~((nm)^(2/3) log C) time algorithm for computing mincost flow (or mincost 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 mincost flow problem in planar graphs.
To obtain our result we first give a very simple successive shortest paths based scaling algorithm for unitcapacity mincost 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 wellestablished tools: rdivisions and efficient algorithms for computing (shortest) paths in socalled dense distance graphs.
BibTeX  Entry
@InProceedings{karczmarz_et_al:LIPIcs:2019:11187,
author = {Adam Karczmarz and Piotr Sankowski},
title = {{MinCost Flow in UnitCapacity Planar Graphs}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {66:166:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771245},
ISSN = {18688969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11187},
URN = {urn:nbn:de:0030drops111878},
doi = {10.4230/LIPIcs.ESA.2019.66},
annote = {Keywords: minimumcost flow, minimumcost circulation, planar graphs}
}
Keywords: 

minimumcost flow, minimumcost circulation, planar graphs 
Seminar: 

27th Annual European Symposium on Algorithms (ESA 2019) 
Issue Date: 

2019 
Date of publication: 

06.09.2019 