Finding and Certifying Weighted Minimum Cuts with Cut Queries

Introduction

In this paper we study the problem of finding the global minimum-cut value of an undirected graph with arbitrary nonnegative real edge weights using cut queries. A cut query to a graph $G=(V,w)$ specifies some subset $S\subseteq V$ and returns the total weight $c_G(S)=w(S,V\setminus S)$ of edges with exactly one endpoint in $S$. Write $n=|V|\ge2$ and $\lambda(G)=\min_{\emptyset\ne S\subsetneq V}c_G(S)$. We give new upper bounds for computing $\lambda(G)$ in both the deterministic and nondeterministic cut query models. As usual in the cut query setting, we count only oracle calls; exact arithmetic and offline computation are unrestricted.

Minimum cuts have repeatedly shown themselves to have a great deal of structure that allows for efficient descriptions. One result of this form concerns the cut dimension. For a graph $G$ with $m$ positive-weight edges, represent each minimum cut by the characteristic vector of its edges in $\{0,1\}^{m}$. The cut dimension of $G$ is the dimension of the span of these vectors over all minimum cuts. Graur, Pollner, Ramaswamy, and Weinberg [11] introduced the cut dimension as a lower-bound technique for the deterministic cut-query complexity of global minimum cut. They proved an $n+1$ upper bound for the analogous dimension of minimum $s$–$t$ cuts, even in directed weighted graphs, but left open the question of how large the cut dimension of global minimum cuts could be. Lee, Li, Santha, and Zhang [15] then showed that the cut dimension of global minimum cuts is at most $2n-3$, and that this bound is tight. Faced with this obstruction to proving larger lower bounds, they introduced the $\ell_1$-approximate cut dimension, a generalization with the potential to give stronger lower bounds. They showed an infinite family of $n$-vertex graphs, with $n=3k+1$, whose $\ell_1$-approximate cut dimension is $2n-2$ and left showing larger lower bounds as an open question.

Later, Auza and Lee [4] showed that, up to an additive term of at most one, the $\ell_1$-approximate cut dimension equals the linear-query certificate complexity of minimum cut. A linear query is more general than a cut query and may ask for any linear combination of the edge weights. Here we study certificates restricted to cut queries, resulting in a potentially even larger quantity that is still a lower bound on deterministic cut query complexity. A cut-query certificate for a graph $G$ is a set of queries $Q$ such that every nonnegatively weighted graph $G'$ on the same vertex set that agrees with $G$ on all queries in $Q$ has the same minimum-cut value. The certificate queries may be chosen with full knowledge of $G$. Certifying that the minimum-cut value is at most $\lambda(G)$ is easy: just query a shore realizing it. The hard part is certifying that no shore can achieve a smaller value.

We show that the cut-query certificate complexity of minimum cut is $O(n\log^2(2n))$. Consequently, neither cut-query certificate complexity nor $\ell_1$-approximate cut dimension can yield a larger deterministic query lower bound for minimum cut. This is yet another way in which minimum cuts are simple: a nearly-linear number of cut queries suffices to fix the minimum cut value in a graph. The key ingredient in our proof is a way to certify the existence of an $s$–$t$ flow of a given feasible value using just $O(n)$ cut queries.

With another lower bound route blocked off, we turn to deterministic algorithms for finding a global minimum cut. In the randomized case, this question has essentially been solved. We know randomized $\widetilde{O}(n)$ cut query algorithms for both simple unweighted graphs [RSW18] and weighted graphs [MN20]; for simple graphs the bound was improved to $O(n)$ in [AEG+22].

In the deterministic case, a simple graph can be reconstructed with $O(n^2/\log n)$ cut queries by simulating the additive queries of Grebinski and Kucherov [9], and this was the best bound known until Anand, Saranu­rak, and Wang [5] gave an $\widetilde{O}(n^{5/3})$ algorithm. Kenneth-Mordoch [KM26] recently improved this to $O(n^{3/2}\log^2(2n))$ cut queries.

For arbitrary nonnegative real weights, however, the best previously known upper bound was the trivial one from reconstructing the graph, which uses $\Theta(n^2)$ cut queries, far from the lower bound of $2n-2$. We give a deterministic algorithm using $O(n^{3/2}\log^3(2n)(\log\log(2n))^2)$ cut queries for the weighted case, within a $\log(2n)(\log\log(2n))^2$ factor of the current best unweighted bound. With the same number of queries the algorithm can return every minimum cut of $G$, not just one.

The recent deterministic algorithms for simple graphs [5 KM26] use maximum-flow and minimum $s$–$t$-cut algorithms. Our algorithm instead follows the two-respecting-cut approach of Karger [12]. Karger’s nearly-linear time randomized algorithm finds $O(\log n)$ spanning trees of the input graph such that, with high probability, some minimum cut contains at most two edges of one of these trees; such a cut two-respects the tree. This reduces the problem to finding a minimum cut among those that two-respect a given tree. Gawrychowski, Mozes, and Weimann [10], building on Mukhopadhyay and Nanongkai [MN20], gave a simple deterministic algorithm for this fixed-tree problem. While they did not explicitly state the algorithm in the cut query model, it is easily adapted to this model: we show in § 12 how to implement their reduction with $O(n\log n)$ deterministic cut queries, even when the supplied tree has edges absent from the input graph. Thus the remaining problem is to find a small family of trees such that a minimum cut two-respects at least one of them.

Karger obtains the trees by sparsifying the graph with random sampling and using a spanning-tree packing [12]. We do not know how to construct such a sparsifier with a comparable deterministic cut-query bound. Instead, we construct a weaker object, a weak skeleton. After handling zero minimum cuts separately, we use $O(n^{3/2}\log^3(2n)(\log\log(2n))^2)$ cut queries to construct an explicit nonnegative weighted graph $H$ on $V(G)$ such that $\lambda(H)\ge\lambda(G)$ and every minimum cut shore $S^*$ of $G$ satisfies $c_H(S^*)\le\frac{5}{4}\lambda(G)$. In particular, every minimum cut shore $S^*$ of $G$ is a $5/4$-approximate minimum cut of $H$. We then construct a family of $O(\log n)$ spanning trees of $H$ such that every $5/4$-approximate minimum cut of $H$ crosses at most two edges of some tree in the family (Lemma 17). This step uses only the explicit graph $H$ and requires no further queries to $G$. Searching these trees with cut queries to $G$ finds an exact minimum cut in another $O(n\log^2 n)$ queries.

§ 2 gives an overview of the certificate proof. § 3 gives a roadmap of the deterministic algorithm, and § 4 and § 5 explain how we construct a weak skeleton via a tree cut sparsifier. Complete proofs are given in § 6 to § 12.

Lean Formalization As part of this work we have developed a library for cut-query algorithms in Lean 4 [14], available at https://github.com/troyjlee/cut-query-complexity. The library formalizes the main certificate and deterministic cut-query theorems of this paper together with their central ingredients, as well as many previous cut-query results on global minimum cut, $s$–$t$ minimum cut and all-pairs minimum cut. We hope that this library will make it easier for others working on cut-query algorithms to formalize their results in Lean. Appendix § 15 records the correspondence between the named results of this paper and the Lean statements, including differences in formulation and the few claims that are not formalized.

Certifying a lower bound with few cut values

Define $\operatorname{cert}(G)$ to be the minimum size of a family $\mathcal{Q}$ of cuts such that

The competing graph $G'$ has the same vertex set and may put positive weight on any pair, including a nonedge of $G$. Equivalently, $\operatorname{cert}(G)$ is the nondeterministic cut-query complexity of determining $\lambda(G)$ on input $G$: the query shores may be provided by an all-knowing prover with knowledge of $G$, but their answers must determine the minimum-cut value uniquely. In particular $\operatorname{cert}(G)$ is a lower bound on the number of cut queries that any deterministic algorithm computing $\lambda$ on nonnegatively weighted graphs makes on input $G$: the shores it asks on $G$ are answered identically by every consistent $G'$, so its output, which is $\lambda(G')$, equals $\lambda(G)$.

Fix $\lambda= \lambda(G)$ and query an optimum shore for the upper bound. If $\lambda= 0$, this already certifies the optimum by nonnegativity. Otherwise, the difficulty is to force every nontrivial cut to have value at least $\lambda$.

For $s$–$t$ cuts there is a clear strategy to lower bound their value: a feasible $s$–$t$ flow of value $c$ certifies that every $s$–$t$ cut has value at least $c$. A first thought is to exhibit such a flow edge-by-edge, but in some weighted graphs every maximum $s$–$t$ flow uses $\Omega(n^{2})$ edges, making this strategy too expensive.

Our key ingredient is a way to certify the existence of a feasible $s$–$t$ flow of value $c$ using $O(n)$ cut queries. We describe the flow implicitly through an optimal dual solution to an auxiliary minimum-cost flow problem. The dual solution is represented by one potential per vertex, and a carefully chosen tree $T$ encodes these potentials. Complementary slackness then forces every non-tree edge to carry its full capacity in a direction determined by $T$. We learn the total incoming and outgoing non-tree flow at each vertex using a constant number of cut queries. These totals determine the remaining divergence that the tree must supply so that the full flow has divergence $c$ at $s$, $-c$ at $t$, and zero elsewhere. We explicitly learn the tree-edge capacities with $O(n)$ cut queries and check that the uniquely determined tree flow respects them. We describe this certificate in the next subsection.

We certify that every nontrivial cut has value at least $\lambda$ by combining the flow certificate with the isolating-cut framework of Li and Panigrahi [17]. The obstacle in adapting their terminal reduction is that it relies on expansion guarantees, which we do not know how to certify cheaply with cut queries. We instead use a terminal-halving argument whose key guarantee is witnessed by a feasible flow, so each halving step can be certified with $O(n)$ cut queries. Specifically, given a terminal set $U$, we retain at most half its terminals in $R \subseteq U$ and certify a feasible flow sending $\lambda/2$ units from each terminal in $U \setminus R$ to $R$, thereby certifying a lower bound of $\lambda$ for every shore avoiding $R$ that contains at least two terminals of $U$. Our construction is described in § 2.2.

A tree describes a certifiable flow

A signed flow on $V$ is a function $f: V \times V \to\mathbb{R}$ satisfying $f_{uv} = -f_{vu}$ for all $u,v \in V$, where $f_{uv} > 0$ means flow from $u$ to $v$. The flow is feasible in $G$ if $|f_{uv}| \le w_{uv}$ for all $u,v \in V$. Its divergence at a vertex $v$ is the net outflow

the sum over $u$ of the flow from $v$ to $u$, so that a source has positive and a sink negative divergence. Every feasible flow satisfies $c_G(S) \ge\left|\sum_{v \in S} b_v\right|$ for every cut.

The key novelty in our global mincut certificate is the following lemma.

that $b$ admits a feasible flow in every consistent graph. The queried shores depend only on $T$ and the fixed vertex labels. In particular, an $s$–$t$ minimum-cut shore and value have a certificate of at most $4n$ queries. For fixed disjoint nonempty terminal sets $A, B \subseteq V$, their minimum separating-cut value has an $O(n)$ cut-query certificate.

To prove Lemma 2, label the vertices $0,\ldots,n-1$. For each pair $\{u,v\}$ with $u<v$, assign the auxiliary cost $a_{uv}=2^{un+v}$, and put $a_{vu}=-a_{uv}$. The sum of the costs around any simple cycle is nonzero for every choice of signs: the largest power of two exceeds the sum of all smaller powers. We then choose a feasible flow $f$ with divergence $b$ minimizing $\sum_{u<v}a_{uv}f_{uv}$.

By complementary slackness for minimum-cost flows (see Bertsekas [7 Sections 1.2.3 and 2.3]), there are vertex potentials $p_v$ such that, for the reduced costs $\rho_p(u,v)=a_{uv}-p_u+p_v$, a negative reduced cost forces $f_{uv}=w_{uv}$ and a positive reduced cost forces $f_{uv}=-w_{uv}$. Thus every unsaturated edge has zero reduced cost. The pairs with zero reduced cost form a forest: around any cycle of such pairs, the identities $a_{uv}=p_u-p_v$ would telescope to a zero signed cost sum, contrary to our choice of costs.

The vertex potentials have one additive degree of freedom on each component of the zero-reduced-cost forest: a common shift preserves all potential differences, and hence all reduced costs, within that component. We use this freedom to extend the forest to a spanning tree while preserving complementary slackness. Choose a component and a pair crossing it with minimum absolute reduced cost, and add the same constant to every vertex potential in the component until that pair has reduced cost zero. By this choice of crossing pair, no reduced cost reverses sign, so $f$ still satisfies the same optimality conditions. Each step merges components; repeating produces a spanning tree $T$ of pairs with zero reduced cost. Root $T$ at any vertex $r$ and normalize $p_r=0$. The equations $p_u-p_v=a_{uv}$ along tree edges then determine all vertex potentials, and hence every non-tree reduced cost. Thus $T$ encodes the direction in which each non-tree pair is saturated. This applies even to pairs absent from $G$, and $T$ may itself contain zero-capacity edges. The full construction and proof appear in § 7.1.

It remains to check that this prescribed non-tree flow can be completed on $T$ to have divergence $b$. First query all singleton cuts and the two-vertex cuts for tree edges. By the well-known fact that for two disjoint sets $A, B$