Skip to content
Preprint

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

Oct 2026 · 0 citations · 17 references
Computer Science

TL;DR

A simple deterministic algorithm is given that finds a global minimum cut using $\tilde O(\min\left\{ n\delta,n^2/\delta \right\})$ cut queries, which equals $\tilde{O}(n^{3/2})$ in the worst case, where $\delta$ is the minimum degree of the graph.

Abstract

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\delta,n^2/\delta \right\})$ cut queries, which equals $\tilde{O}(n^{3/2})$ in the worst case, where $\delta$ 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 $\delta$.

View source

Similar papers

Preprint Oct 2026

Directed Global Minimum Cut in Almost-Linear Time

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 th...

Henry L. Fleischmann, Jason Li, Thatchaphol Saranurak et al. · 3 citations · ⚡1
Sep 2026

Maximum Matching Size for Bounded Arboricity Graphs in the Dynamic Graph Stream Model using ~O}(n2/3) space

The paper presents a one-pass algorithm in the insert-delete graph stream model that returns a $(1+\varepsilon)(\alpha+2)$-approximation for the size of the maximum matching in a graph of arboricity at most $\alpha$. The algorithm uses $O(\varepsilon^{-4/3}\alpha^{4/3}n^{2/3} \text{polylog} n)$ space. For constant $\al...

A. Mcgregor · 0 citations
Preprint Sep 2026

More Efficient Parallel $(\Delta+1)$-Edge Coloring

The deterministic algorithm represents a $\tilde{O}(\Delta)$ improvement on span and $\tilde{O}(\Delta^2)$ on work compared to their algorithm, and the randomized algorithm improves the span and work by $\tilde{O}(\Delta^2)$ and $\tilde{O}(\Delta^3)$ factors, respectively.

Jeremy T. Fineman, Seyed Ali Mohammadi · 0 citations
Preprint Oct 2026

The Six-Dimensional Tarski Problem is $\Omega(\log^3 n)$-Hard

We study the deterministic query complexity of finding a fixed point of a monotone function $f:[n]^d\to[n]^d$, where querying $x$ returns $f(x)$. For fixed $d\ge2$, earlier work established a lower bound of $\Omega((\log n)^2)$ and an upper bound of $O_d((\log n)^{\lceil(d+2)/3\rceil})$ for the query complexity. Very r...

Kristóf Zólomy · 0 citations
Preprint Oct 2026

Improved Quasi-Polynomial-Time Approximation for Maximum Independent Set

We give a deterministic quasi-polynomial-time algorithm for the maximum independent set problem. If an $N$-vertex graph contains an independent set of size $2^{-t}N$, where $t$ is an integer with $1\le t\le\sqrt{\log N}/12$, then our algorithm finds an independent set of size $2^t$ in time $N^{O(t)}$. This gives an app...

Zhao Song · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.