CS Paper Radar

Faster high-accuracy multicommodity flow in dense graphs

Chenxin Dai, Alicia Stepin, Colin Tang

cs.DS math.OC ·submitted 2026-10-05 16:40 UTC · v1
publishedhot direction

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.

Comment
ITCS27 submission with updates

Closest papers

Nearest neighbours by meaning across the whole index.

Time-Optimal APSP and Matrix Multiplication in Classes of Linear Neighborhood Complexity

cs.DS cs.CCcs.DMmath.CO ·2026-08-25 ·Édouard Bonnet, Julien Duron, Marcin Pilipczuk, Marek Sokołowski, Szymon Toruńczyk
similarity 0.68
Abstract · 31 pages, 5 figures

The notion of linear neighborhood complexity is a very general structural assumption on a graph class, covering most classes of sparse graphs such as planar graphs, graphs excluding a fixed (topological) minor, or bounded expansion graphs, as well as many structured classes of dense graphs, such as graphs of bounded clique-width, twin-width, merge-width, or flip-width. In this work, we present $O(n^2)$-time optimal algorithms for $n$-vertex graphs coming from a class of linear neighborhood complexity for the following problems: $\bullet$ All-Pairs Shortest Paths, $\bullet$ the multiplication of the adjacency matrix $M$ of the input graph with any $n \times n$ matrix. More specifically, after a quadratic preprocessing, we can multiply $M$ with any $n$-vector in $O(n)$ time. This solves several questions raised in [Bonnet, Kim, Geniet, Moon; ICALP '26], and improves and generalizes results in several other recent papers [Bonnet, Giocanti, Ossona de Mendez, Thomassé; STACS '23], [Bannach, Marwitz, Tantau; STACS '24], [Anand, van den Brand, McCarty; NeurIPS '26], [Kozma, Opler '26], and [Cardinal, McCarty, Yuditsky '26]. We also extend our results to classes of bounded VC density. In classes of linear neighborhood complexity, we also give a triangle-detection algorithm in randomized linear time $O(n+m)$ in $n$-vertex $m$-edge graphs, a $K_4$-detection algorithm in randomized $O(n \log^5 n + m \log n)$ or deterministic $O(n^2)$ time, and a $K_5$-detection algorithm in randomized $O(n \log^9 n + m \log^5 n)$ time.

0.37

Faster Minimum k-Cut I: Simple and Sparse Weighted Graphs

cs.DS ·2026-08-17 ·Jason Li, Trevor Vaughn
similarity 0.67
Abstract

The minimum $k$-cut problem asks for the fewest edges whose removal leaves an input graph with at least $k$ connected components. Previously, the best algorithm for simple graphs ran in $O_k(n^{(1-\varepsilon)k+O(1)})$ time~\cite{HL22}, showing that the \(n^k\) barrier can be broken up to a polynomial overhead. We give the first $\widetilde O_k(n^{ck})$-time algorithm for Minimum $k$-Cut on simple graphs for an absolute constant $c<1$. More precisely, the running times are $\widetilde O(n^2)$ for $k=3$, $\widetilde O(n^{55/19})$ for $k=4$, and $\widetilde O(n^{4.112007})$ for $k=5$; for every $k\ge6$, the running time is \[ k^{O(k^2)}n^{1+(6k-6)\frac{k-1.749614}{7k-10}}(\log n)^{O(k^2)}, \] whose exponent is $\frac67k-0.132\ldots+O(1/k)$. The algorithm combines three ingredients. First, for weighted Minimum $k$-Cut we give a randomized \[ k^{O(k^2)}n^{k-2}(m+n)\log^3(n) \] -time algorithm: it perturbs the edge weights so that any minimum $k$-cut has a side with boundary strictly smaller than average. These then cut few edges of some tree in a logarithmic-size sample from a tree packing with high probability. After we enumerate them, we recursively compute $(k-1)$-cuts to complete them to the $k$-cuts of which they were a part. A variant of the perturbation and processing the entire packing support give a deterministic $k^{O(k^2)}n^{k+O(1)}$-time variant. Second, for cut size $s$, we give an improved FPT algorithm using a near-linear-time construction of an $(O(s\log^2 n\log\log n),s)$ edge-unbreakable tree decomposition with $O(s\log^2 n\log\log n)$ adhesion; this also gives a near-linear-time approximation algorithm for Minimum $k$-Cut. Third, we refine the border/island framework of~\cite{HL22}, using rectangular matrix multiplication to recover singleton islands and balancing it against the improved FPT algorithm.

0.36

Near-Optimal Parallel $M$-Matrix Scaling

cs.DS math.OC ·2026-10-15 ·Chih-Hung Liu, Aaron Sidford, Ta-Wei Tu
similarity 0.65
Abstract

In this paper we consider the problem of computing a positive diagonal scaling of a $d \times d$ symmetric $M$-matrix so that all row and column sums are $1$. We provide a poly-logarithmic iteration algorithm that solves this problem to high accuracy, where the cost of each iteration is dominated by the cost of solving a Laplacian system. This improves upon the recent $\tilde{O}(d^{1/3})$ iteration bound of [Vladu STOC 2025] and yields a randomized algorithm for the problem that runs in near-linear time and poly-logarithmic parallel depth.

0.52

Faster Minimum k-Cut II: Improved Randomized and Deterministic Algorithms for Weighted Graphs

cs.DS ·2026-08-17 ·Trevor Vaughn
similarity 0.64
Abstract

The Minimum $k$-Cut problem asks for a minimum-weight set of edges whose removal leaves an undirected weighted graph with at least $k$ connected components. We consider only $k\ge3$. The fastest previous algorithm for weighted graphs ran in $n^{k-2}(m+n)(\log n)^{O(k^2)}$ randomized time~\cite{LV26}; on dense graphs this is $\widetilde O_k(n^k)$, and for $k=3$ it gives an $\widetilde O(nm)$-time algorithm. We improve the dense-graph exponent from $k$ to $k-1$ and obtain the same exponent deterministically. After aggregating parallel edges in $O(m)$ time, our randomized algorithm runs with high probability in \begin{equation*} k^{O(k^2)}n^{k-1}\log^2n \end{equation*} time, while our deterministic algorithm runs in \begin{equation*} k^{O(k^2)}n^{k-1}\log^{O(1)}n \end{equation*} time. In particular, weighted Minimum $3$-Cut can be solved in $O(n^2\log^2 n)$ randomized time and in $\widetilde O(n^2)$ deterministic time. The algorithms have two main components. First, we give a faster algorithm for weighted Minimum $3$-Cut. After handling optima with a very small side and optima with two light sides, the remaining optimum has a unique structured side. Tree packing reduces its completion to a batched collection of $2$-respecting cut problems. Second, we reduce Minimum $k$-Cut to Minimum $3$-Cut by enumerating a bounded family of light-cut candidates and recursively completing either side of each candidate. If the enumeration produces too many cuts, then we can instead produce an optimum $k$-cut directly. We derandomize the $3$-cut algorithm using a deterministic near-minimum-cut skeleton, and derandomize the reduction using a specialized $4$-cut algorithm using the skeleton, the constructive light-cut bounds, and the deterministic spectral sparsifier of \cite{BSS12}.

0.23

Approximating the Girth of an Undirected, Weighted Graph for Larger Approximation Factors

cs.DS ·2026-10-16 ·Eliyahu Yablon
similarity 0.63
Abstract

The girth of a weighted undirected graph is defined as the length of a shortest cycle in the graph. In this paper, we give a randomized $O\left(m^{1+2/(k-1)} n^{1/(k-1)}\right)$ algorithm to approximate the girth of a graph with $n$ vertices and $m$ edges to within a factor of $k$ for any real $k$. We assume that all edge weights are non-negative. For sufficiently high approximation factors, our algorithm outperforms the state of the art by polylogarithmic factors. Specifically, for approximation factors $k = c\frac{\log n}{\log \log n}$ where $c>5$, our algorithm gives a runtime of $O\left(m (\log n)^{5/c}\right)$, while instantiating the previous best $k$-approximation algorithms with $k = c\frac{\log n}{\log \log n}$ yields a running time of $O\left( \frac{cn (\log n)^{2 + 4/(3c)} }{\log \log n} + m\log n\right)$ (Kadria, Roditty, and Vassilevska Williams, arXiv:2607.00938). Furthermore, the algorithm presented here is conceptually simple, has relatively small constants, eschews single-source shortest path and sparse spanner algorithms, and employs a new technique, which we call ``random filtering.'' That being said, the basic algorithm returns only a numerical estimate for the girth, rather than a witness cycle.

0.18

Combinatorial Minimum Cost Flow in Almost-Linear Time on Dense Graphs

cs.DS ·2026-10-23 ·Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak
similarity 0.63
Abstract · 101 pages

We give a combinatorial algorithm that computes an exact minimum-cost flow in $n^{2+o(1)}$ time. This is the first combinatorial improvement since Goldberg-Tarjan [GT87], and is almost optimal in dense graphs. All previous faster algorithms, including the almost-linear-time algorithm of Chen et al. [CKL+22], rely on interior-point methods. Our main conceptual contribution is a black-box reduction from exact minimum-cost flow on general graphs to its approximation on DAGs, with only an $n^{o(1)}$ loss on the running time. This reduction allows future work on combinatorial minimum-cost flow to focus on DAGs, typically much easier to handle than general graphs. Our $n^{2+o(1)}$-time algorithm follows by combining this reduction with a simple augmenting-path-based approximation algorithm on DAGs. The reduction is based on a new structural result, called a flow-cost-preserving DAG projection. Given an arbitrary directed graph, this construction produces a DAG that approximately preserves both the congestion of flows and their cost up to a small loss.

0.48

Flows in High Degree Places: Sublinear Spanning Tree Congestion

cs.DS ·2026-11-09 ·D Ellis Hershkowitz, Richard Z Huang
similarity 0.63
Abstract

The congestion of a spanning tree $T$ of graph $G$ is the maximum congestion of an edge of $T$ if each edge of $G$ is routed on $T$. Prior work showed that obtaining a minimum congestion spanning tree is NP-hard to approximate within $6/5$, yet the only known approximation algorithm is a trivial $n/2$-approximation from returning any spanning tree of the graph. We give a simple poly-time $\tilde{O}(n^{6/7})$-approximation for minimum congestion spanning tree on $n$-vertex graphs. We obtain this result via a $\tilde{O}(m^{2/3})$-approximation, where $m$ is the number of edges. Our algorithm is based on a new \textit{flow-or-degree decomposition} which deletes a small number of edges so that each remaining component either has low degree or admits a low congestion flow. We also show that, assuming the Small Set Expansion Hypothesis, it is NP-hard to $O(1)$-approximate this problem, even on graphs of constant maximum degree.

0.04

Finding Hypercliques Faster Than Brute Force

cs.DS cs.CC ·2026-11-03 ·Josh Alman, Baitian Li, Neha Pant, Kevin Pratt, Ryan Williams
similarity 0.62
Abstract

We show that for any fixed $k$, there exists $\varepsilon_k > 0$ such that, given a $(k-1)$-uniform hypergraph $H$ on $n$ vertices, one can count the number of $k$-hypercliques in $H$ in $O(n^{k-\varepsilon_k})$ time. This refutes the hyperclique conjecture of Lincoln, Vassilevska Williams, and Williams (SODA 2018). Our result follows from the uniform construction of a family of arithmetic circuits of size $O(n^{k-\varepsilon_k})$ for the $k$-hyperclique tensor, a natural higher-order generalization of the matrix multiplication tensor. We obtain two corollaries. First, for every $k$, there exists $\varepsilon > 0$ such that Max-$k$SAT can be solved in $2^{(1-\varepsilon)n} \cdot \mathrm{poly}(m,n)$ time. Second, for every $k$, there exists $\varepsilon > 0$ such that arithmetic progressions of length $k$ in subsets of $\{0,1,\ldots,n\}$ can be detected in $n^{2-\varepsilon}$ time. Both corollaries refute other prominent conjectures in the literature.

0.23