# Faster high-accuracy multicommodity flow in dense graphs

Preprint · Chenxin Dai, Alicia Stepin, Colin Tang

- Archive id: arxiv:2610.06665
- Published: 2026-10-05
- arXiv: https://arxiv.org/abs/2610.06665
- Source URL: https://arxiv.org/abs/2610.06665
- PDF: https://arxiv.org/pdf/2610.06665
- Provenance: arxiv

## Abstract

We give a fast algorithm for solving min-cost $k$-commodity flow. The basic idea is to construct an auxiliary linear program that has low rank and whose minimum value is at most $1/k$ times the minimum value of the original problem (thus, solving this auxiliary linear program will make at least $1/k$ fraction of progress in the original problem). Low-rank linear programs can be solved quickly using black-box techniques. Thus, our algorithm runs in time $\\tilde{O}(\\operatorname{poly}(k)(n^{2.5}+m\\sqrt{n}))$ on a directed graph with $n$ vertices and $m$ edges. We do not rely on any fast matrix multiplication.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.