Minimum Cost Flow in the CONGEST Model

We consider the CONGEST model on a network with n nodes, m edges, diameter D, and integer costs and capacities bounded by poly n. In this paper, we show how to find an exact solution to the minimum cost flow problem in n(1/2+o(1))(root n + D) rounds, improving the state of the art algorithm with running time m(3/7+o(1))(root nD(1/4) + D) [16], which only holds for the special case of unit capacity graphs. For certain graphs, we achieve even better results. In particular, for planar graphs, expander graphs, n(o(1))-genus graphs, n(o(1))-treewidth graphs, and excluded-minor graphs our algorithm takes n1/2+o(1)D rounds. We obtain this result by combining recent results on Laplacian solvers in the CONGEST model [3,16] with a CONGEST implementation of the LP solver of Lee and Sidford [29], and finally show that we can round the approximate solution to an exact solution. Our algorithm solves certain linear programs, that generalize minimum cost flow, up to additive error epsilon in n(1/2+o(1))(root n + D) log(3) (1/epsilon) rounds.