CS Paper Radar

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

Jason Li, Trevor Vaughn

cs.DS ·submitted 2026-08-17 05:57 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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

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

Tight Quantum Query Bounds for Minimum Cut and Multicut on Dense Graphs

cs.DS cs.CC ·2026-11-13 ·Tianhang Lu, Runtian Ren, Shengcai Liu
theory similarity 0.70
Abstract

We determine the dense worst-case quantum query complexity of exact minimum multicut on simple unweighted undirected graphs. With at most $k$ explicit demand pairs, our adjacency-array algorithm uses $\OO(n+\min\{m,n^{3/2}\sqrt{k}\})$ queries; a matching lower bound holds for every $1\le k\le\lfloor n/2\rfloor$ and sufficiently large $n$, with constants uniform in $k$. In particular, the $k=1$ case gives an $\OO(n^{3/2})$ query algorithm for prescribed $s$--$t$ cut. The upper bound combines degree-sensitive spectral estimates of local improvement with refinement by unions of label classes. These steps retain every original optimum and permit exact acquisition without an additional label-count factor. Separately, we prove an $Ω(n^{3/2})$ global minimum-cut lower bound on dense connected graphs, matching the existing upper bound up to polylogarithmic factors. It holds for the value and for any optimum shore, even with known degrees and sorted neighbor arrays; regular hard instances have balanced optimum cuts. Both lower bounds use degree-preserving switches and classify optimum outputs across a hidden threshold. Our upper bound concerns input queries, not total running time: computation on acquired data may be exponential, even in the single-demand case. Matching bounds at each prescribed sparse edge count are not established.

0.12

Deterministic Global Minimum Cut Using $\tilde{O}(n^{3/2})$ Cut Queries

cs.DS ·2026-10-16 ·Yotam Kenneth-Mordoch
published similarity 0.69
Abstract · Accepted at SOSA 2027

Finding a global minimum cut in an unweighted graph is a fundamental task in the cut-query model. While there exists a randomized algorithm for this task using $\tilde O(n)$ queries, known deterministic algorithms use $\tilde{O}(n^{5/3})$ queries. We improve upon this result and give a simple deterministic algorithm that finds a global minimum cut using $\tilde O(\min\left\{ nδ,n^2/δ\right\})$ cut queries, which equals $\tilde{O}(n^{3/2})$ in the worst case, where $δ$ is the minimum degree of the graph. The key ingredient in our approach is an efficient maximum $s,t$-flow algorithm, for the case when the minimum $s,t$-cut has value at most $δ$.

0.28

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

cs.DS ·2026-11-05 ·Zhaienhe Zhou
similarity 0.69
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 Algorithms for Disjoint Paths in DAGs and Two Disjoint Shortest Paths

cs.DS ·2026-11-01 ·Yang Cao, Haoran Qi, Hanzhi Wang
similarity 0.69
Abstract

For $k$ vertex-disjoint paths with prescribed endpoints in a directed acyclic graph (DAG), the $O(mn^{k-1})$-time pebbling algorithm of Fortune, Hopcroft, and Wyllie [TCS 1980] has remained the fastest for every $k\geq3$ for over four decades, even when the paths must be shortest. We break this bound for every $k\geq3$ with randomized algorithms running in expected $O_k(m+n^{k-3+ω+\varepsilon})$ time for every $\varepsilon>0$, where $ω<2.372$ is the matrix multiplication exponent; this is $O_k(m+n^{k-0.62})$. For two disjoint shortest paths, we find the paths as fast as we detect them: in expected linear time on DAGs and on undirected graphs with polynomially bounded integer weights, and in expected $O(\min\{mn,n^{ω+\varepsilon}\})$ time on directed graphs whose cycles have positive weight, which on dense graphs is $o(mn)$ even for detection. All algorithms evaluate a polynomial whose monomials are the solutions: a new first-collision circuit speeds up the evaluation in DAGs, and a correlated extraction step at cuts crossed once by every path finds a solution at the cost of a constant number of evaluations.

0.20

Reachability Diameter: Beyond the Square-Root Barrier, with Polynomial Hardness

cs.DS ·2026-11-03 ·Hector Tierno, Shuang Yang
theory similarity 0.68
Abstract

The reachability diameter of a directed graph is the maximum finite shortest-path distance across all pairs of vertices. It has received recent attention under this name, although the underlying quantity has long played a central role in shortcut set and parallel reachability. Notably, Bals et al. establish hardness for every polynomial-factor approximation in nearly-linear time for weighted digraphs. Yet they give $n^{1/2+o(1)}$-approximation in the unweighted regime with nearly-linear running time, and their conditional lower bounds rule out certain constants only, leaving open whether polynomial loss is necessary. We give a randomized algorithm that estimates the reachability diameter of an unweighted digraph within a factor $n^{1/3+o(1)}$, with high probability, in $\widetilde{O}(m+n)$ time. We complement our algorithm with a lower bound conditional on the 3-uniform Hyperclique hypothesis, ruling out an $n^{2/15-\varepsilon}$-approximation in $\widetilde{O}(m+n)$ time for every fixed $\varepsilon\in(0,2/15)$, establishing the necessity of polynomial loss for nearly-linear time algorithms.

0.25

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

cs.DS ·2026-10-16 ·Eliyahu Yablon
similarity 0.68
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

Packing Diverse Shortest Cycles

cs.DS ·2026-10-07 ·Akanksha Agrawal, Fedor V. Fomin, Petr A. Golovach, Vinod Gupta, Yash Hiren More +1 more
theory similarity 0.68
Abstract

Bentert, Fomin, Golovach, Korhonen, Lochet, Panolan, Ramanujan, Saurabh, and Simonov (SODA 2025) initiated the parameterized study of Edge-Disjoint Shortest Cycle Packing: given a weighted graph $G$ and an integer $k$, decide whether $G$ contains $k$ edge-disjoint cycles of minimum weight. They showed that the problem admits an algorithm running in time $n^{O(k^6)}$ and asked whether it is fixed-parameter tractable or $W[1]$-hard parameterized by $k$. We resolve this question by proving that Edge-Disjoint Shortest Cycle Packing is $W[1]$-hard parameterized by $k$, even on unweighted subcubic graphs. The same lower bound also applies to the vertex-disjoint variant. For planar graphs, they provides a construction of a kernel with $O(k^2)$ vertices and an algorithm running in time $k^{O(k)} \cdot n^{O(1)}$, and explicitly asked whether the problem admits a single-exponential algorithm of running time $2^{O(k)} \cdot n^{O(1)}$. Rather than addressing this question in isolation, we introduce a more general framework, Diverse Shortest Cycle Coverage, which asks for $k$ shortest cycles that may overlap in a controlled way while maximizing the total weight of covered edges. This framework simultaneously captures edge-disjoint shortest cycle packing, the problem of finding diverse shortest cycles, and the problem of maximizing edge coverage by shortest cycles. Our main algorithmic result shows that Diverse Shortest Cycle Coverage can be solved on planar graphs in time $2^{O(k)} \cdot n^{O(1)}$, thereby giving a single-exponential algorithm for Edge-Disjoint Shortest Cycle Packing as a special case. The key idea of our algorithm is a structural analysis of the Laminar Shortest Cycles Tree, a tree-like decomposition that reveals a laminar interaction pattern among shortest cycles in planar graphs and enables an efficient dynamic programming algorithm.

0.24