Skip to content
DraconiticResearch
Search Sources API
206,690 studies31 sourcesUpdated 50 min ago
PreprintCC BY-NC-SA 4.0arXiv

Faster high-accuracy multicommodity flow in dense graphs

  • Chenxin Dai
  • Alicia Stepin
  • Colin Tang
Open at sourcePDFDOICite

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 Õ(poly(k)(n2.5+m√n)) on a directed graph with n vertices and m edges. We do not rely on any fast matrix multiplication.

Related

  1. Path Decompositions of Sparse Graphs via Gaussian Sweeps and Faster Exponential Algorithms
    Serge Gaspers
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. The singularity probability of dense random regular graphs
    Zeyan Song, Hanchao Wang, Shengyan Yin +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv
  3. Seeking the dense half in K4-free graphs
    Ignacy Buczek, Andrzej Grzesik, Piotr Kuc
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. The Erd\H os-Sós conjecture in dense graphs
    Bruce Reed, Maya Stein
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Counting cographs in locally dense graphs
    Hyunwoo Lee
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{dai2026faster,
  title = {{Faster high-accuracy multicommodity flow in dense graphs}},
  author = {Chenxin Dai and Alicia Stepin and Colin Tang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.06665},
  eprint = {2610.06665},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.06665},
  note = {CC BY-NC-SA 4.0},
}
RIS
TY  - UNPB
TI  - Faster high-accuracy multicommodity flow in dense graphs
AU  - Chenxin Dai
AU  - Alicia Stepin
AU  - Colin Tang
PY  - 2026
DA  - 2026/10/05
PB  - arXiv
DO  - 10.48550/arxiv.2610.06665
UR  - https://arxiv.org/abs/2610.06665
AB  - 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 Õ(poly(k)(n^2.5+m√n)) on a directed graph with n vertices and m edges. We do not rely on any fast matrix multiplication.
ER  -