CS Paper Radar

A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization

Alina Ene, Huy L. Nguyen

cs.DS ·submitted 2026-10-18 16:59 UTC · v1

Abstract

We give a strongly polynomial time algorithm for submodular function minimization with overall running time $\widetilde{O}(n^{2}\mathsf{EO}+n^{3})$ time, where $\mathsf{EO}$ is the running time of a single evaluation of the function. Our algorithm improves upon the previously fastest strongly polynomial algorithms of Lee et al. (FOCS 2015), Dadush et al. (SODA 2018), and Jiang et al. (SODA 2024) that run in time $\widetilde{O}(n^{3}\mathsf{EO}+n^{4})$. Similarly to prior works, our work combines a cutting plane algorithm with the combinatorial arc-finding framework of Fleischer et al. (JACM 2001). We achieve our faster running time by developing an algorithm that runs the cutting plane method end to end, without restarting after discovering arcs and contracting strongly connected components.

Closest papers

Nearest neighbours by meaning across the whole index.

All minimum cuts of symmetric submodular functions

cs.DS math.COmath.OC ·2026-11-05 ·Chao Xu
hot direction similarity 0.63
Abstract

We compute Cunningham's canonical decomposition of a symmetric submodular function on $n$ elements in $O(n^3)$ time. The decomposition represents all minimum cuts in linear space. For the pair $s,t$ produced by Queyranne's algorithm, we construct in $O(n^2)$ time a digraph representing exactly the minimum $st$-cuts of the function. Using this construction in Chekuri and Xu's decomposition algorithm gives the cubic bound.

0.26

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

cs.DS ·2026-08-17 ·Jason Li, Trevor Vaughn
similarity 0.61
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

Symmetric Submodular Minimization from Comparisons

cs.DS ·2026-10-07 ·James Fox, David P. Woodruff
theory similarity 0.60
Abstract

Given value-oracle access to a symmetric submodular function $f:2^V\to\mathbb{R}$ with $|V|=n$, a nontrivial minimizer can be found using $O(n^3)$ value queries. We study the weaker comparison model, in which a query on $S,T\subseteq V$ reveals only whether $f(S)$ is smaller than, equal to, or larger than $f(T)$. We give a deterministic polynomial-time algorithm that finds a nontrivial minimizer of any symmetric submodular function using $O(n^3)$ comparisons, matching the best-known deterministic value-oracle bound despite not knowing the function values. More generally, the same $O(n^3)$-comparison bound holds for minimization over the nonempty members of any downward-closed family. Our algorithm combines the minimum-capacity ordering recently introduced by Iwata and Konno with the contraction framework of Goemans and Soto. Applying this result to weighted graph cut functions resolves the main open question of Cohen-Addad et al., who gave an $\widetilde{O}(n^3)$-comparison algorithm that runs in exponential time and asked whether a weighted minimum cut can be found in polynomial time using comparisons. For graphs with $m$ edges of integer weight at most $B$, we also give a deterministic polynomial-time algorithm that finds a minimum cut using \[ \widetilde{O}\!\left(n^2+\min\!\left\{mB,\,nB^2\right\}\right) \] comparisons, improving on the $O(n^3)$ bound when $B$ is small. Finally, we show that every randomized algorithm that outputs a minimum cut with probability at least $2/3$ makes $Ω(n \log n)$ expected comparisons in the worst case. Under the stronger assumption that all edge weights are polynomially bounded integers, we obtain an $Ω(n \log \log n)$ expected comparison lower bound. These bounds contrast with the value-oracle model, where no $ω(n)$ lower bound is known even for deterministic algorithms.

0.33

Directed Global Minimum Cut in Almost-Linear Time

cs.DS ·2026-10-07 ·Henry Fleischmann, Jason Li, Thatchaphol Saranurak, Benyu Wang
highly cited similarity 0.59
Abstract · 11 pages, 4 figures

We give a randomized reduction from global minimum cut in a directed graph with $n$ vertices and $m$ weighted edges to maximum-flow computations on graphs of total size $\widetilde{O}(m)$. For polynomially bounded integral weights, this yields the first almost-linear $m^{1+o(1)}$-time algorithm [vdBCK+23], improving the previous $m^{1+o(1)}\min\{\sqrt{n},n/m^{1/3}\}$ bound [CLN+22]. Previous work reduced finding the minimum cut to constructing a 1-respecting arborescence, a directed spanning tree with exactly one edge crossing a minimum cut [CLN+22]. They then construct such a tree by sampling from a $(1+ε)$-approximate arborescence packing, which currently requires superlinear time. Our algorithm sidesteps constructing the packing entirely and relies on a novel iterative arborescence sampling procedure. We show that, after $O(\log n)$ rounds of sampling, our final arborescence 1-respects the minimum cut with constant probability.

0.48

Minimum-Cost $k$-Arborescence Packing in $\tilde O(km+k^4 n)$ Time

cs.DS ·2026-11-05 ·Zhaienhe Zhou
similarity 0.59
Abstract

We give a deterministic, strongly polynomial algorithm running in $\tilde{O}(km+k^4n)$ time that finds $k$ arc-disjoint arborescences of minimum total cost in a directed multigraph with $n$ vertices and $m$ arcs. This significantly improves upon the state of the art for $k \ge 2$ with $k=n^{o(1)}$: the prior fastest weakly polynomial and strongly polynomial algorithms take $\tilde{O}(km\sqrt{n}\log C)$ and $\tilde{O}(kmn)$ time (Gabow and Xu, 1989; Gabow, 1995), respectively. Roughly, our technique can be viewed as a way to apply a linear number of \emph{shortest} augmenting paths in near-linear total time for the special case of the weighted matroid intersection problem between the $k$-fold graphic matroid and the indegree partition matroid. This was previously done in the unweighted case by Gabow (1995), but our approach is different. As an extension, we also obtain a deterministic $\tilde{O}(km^{1+o(1)}+k^5n)$-time algorithm for minimum-cost maximum-cardinality packing of $k$ forests in undirected graphs. In particular, this finds $k$ edge-disjoint spanning trees of minimum total cost, if they exist. The previous fastest algorithm takes $\tilde{O}(kn^2+m)$ time (Gabow and Westermann, 1992).

0.23

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

cs.DS ·2026-08-17 ·Trevor Vaughn
similarity 0.58
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

Differentially Private All-Pairs Min Cut Values

cs.DS ·2026-11-05 ·Anders Aamand, Justin Y. Chen, Mina Dalirrooyfard, Slobodan Mitrović, Sandeep Silwal +1 more
publishedtheory similarity 0.57
Abstract · To appear in SOSA 2027

We study the problem of privately releasing the min cut values of all pairs of vertices in a given $n$-node weighted graph, under the edge-neighboring model. Straightforward application of advanced composition yields an approximate DP algorithm that outputs all min cut values up to $\tilde{O}(n)$ additive error. Prior works [Dalirrooyfard, Mitrovi{ć} and Nevmyvaka, 2023; Aamand et al., 2026] have established that $\tildeΘ(n)$ is the correct bound if the algorithm also needs to output cuts that realize the approximate min cut values. On the other hand, simply outputting the values could be an easier problem, but prior algorithms have been stuck on the $\tilde{O}(n)$ bound. In this work, we give an approximate DP algorithm outputting all-pair min cut values with $\tilde{O}(\sqrt{n})$ additive error, beating the linear error barrier. Our algorithm applies the sparse vector technique [Dwork and Roth, 2014] to maintain a hierarchical decomposition of the vertices based on the min cut structure. We also prove an $Ω(\log^{3/2} n)$ lower bound for this problem.

0.35

A Polynomial Time Algorithm for Finding a Minimum 5-Partition of a Submodular Function

cs.DS math.CO ·2026-11-16 ·Yuhao Liu, Ke Shi, Chao Xu
similarity 0.57
Abstract · 11 pages

Given a real-valued submodular function on a finite ground set, the minimum $k$-partition problem asks for a partition into $k$ nonempty parts minimizing the sum of their function values. We give a polynomial-time algorithm for $k=5$. The idea follows directly from the previous $k=4$ result, where there is precisely one obstruction for generalizing it to $k=5$. We show the special case can be handled by reasoning about a restricted family of $3$-partitions.

0.42