Minimum Cost Flow in the CONGEST Model
share
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)(√(n)+D) rounds, improving the state of the art algorithm with running time m^3/7+o(1)(√(n)D^1/4+D) [Forster et al. FOCS 2021], 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 n^1/2+o(1)D rounds. We obtain this result by combining recent results on Laplacian solvers in the CONGEST model [Forster et al. FOCS 2021, Anagnostides et al. DISC 2022] with a CONGEST implementation of the LP solver of Lee and Sidford [FOCS 2014], 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 ϵ in n^1/2+o(1)(√(n)+D)log^3 (1/ϵ) rounds.
READ FULL TEXT