Finding and Certifying Weighted Minimum Cuts with Cut Queries

Abstract

We study the deterministic and nondeterministic cut query complexity of minimum cut in undirected graphs with arbitrary nonnegative edge weights. For the nondeterministic case, we show that every $n$-vertex graph has an $O(n\log^2(2n))$-query certificate of its exact global minimum-cut value, such that any other nonnegatively weighted graph on the same vertex set that agrees on these queries has the same minimum cut value. A key ingredient is a way to certify a maximum $s$--$t$ flow value with only $O(n)$ cut queries. For the deterministic case we give an algorithm that finds an exact global minimum cut using $O(n^{3/2}\log^3(2n)(\log\log(2n))^2)$ cut queries. Previously no $O(n^{2-\varepsilon})$ deterministic bound was known for arbitrary nonnegatively weighted graphs. The algorithm follows Karger's two-respecting tree approach. The key new ingredient is a deterministic construction of a weak skeleton of the input graph $G$: an explicit weighted graph $H$ in which every minimum cut of $G$ is a $5/4$-approximate minimum cut.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Data Structures & Algorithms

• arXiv preprint · 2 November 2026

  Efficient Proper Agnostic Learning of Halfspaces

  Anindya De, Elchanan Mossel, Shivam Nadimpalli and 1 other
• arXiv preprint · 3 November 2026

  A Constant-Factor Approximation for Capacitated Facility Location with Outliers

  Rajni Dabas
• arXiv preprint · 2 November 2026

  Submodularity Is Barely Testable

  Diptaksho Palit and Yuichi Yoshida
• arXiv preprint · 3 November 2026

  Semidirect sums of tensors and the matrix multiplication exponent

  Baitian Li
• arXiv preprint · 2 November 2026

  Generalized Flows over Time: Complexity, Structure and Algorithm

  Siyuan Chen, Shengminjie Chen, Suixiang Gao and 3 others

All new papers in Data Structures & Algorithms