TL;DR
This paper determines that the cut dimension of any $n$-vertex weighted undirected graph—the dimension spanned by its minimum cut characteristic vectors—is at most $2n - 3$, and proves this bound is tight. Because cut dimension lower-bounds the deterministic query complexity of computing a minimum cut under both cut and linear query models, the authors establish a tight $2n - 3$ barrier for this technique. To push past this limit, they introduce the $\ell_1$-approximate cut dimension, using it to prove a new deterministic lower bound of $2n - 2$ linear queries.
What Problem Does This Paper Address?
While randomized algorithms can compute the minimum cut (mincut) of a weighted graph in nearly linear time with $\tilde{O}(n)$ cut queries, deterministic query complexity has remained largely open. In the query setting, an algorithm learns edge weights by querying cut values $w(\Delta(X))$ or, more generally, arbitrary linear combinations $w^T x$. The best-known deterministic algorithms must learn essentially the entire graph ($\Omega(n^2 / \log n)$ queries), while the best lower bound was only $3n/2 - 2$ (Graur et al., ITCS 2020).
Graur et al. established their lower bound via the cut dimension—the linear dimension of the space spanned by the indicator vectors of all minimum cuts. This paper asks two foundational questions:
- What is the fundamental algebraic limit on the cut dimension of an $n$-vertex graph?
- Can we generalize this linear-algebraic framework to near-minimum cuts to prove stronger query lower bounds?
Methods
The authors provide two complementary proofs of the upper bound $\text{cdim}(G) \le 2n - 3$ and two distinct graph constructions achieving it:
-
Combinatorial Uncrossing & Jain’s Lemma: The authors relate cross-free cut families to laminar set systems. By leveraging Jain's uncrossing technique from survivable network design, they prove that the characteristic vectors of any maximal cross-free subset of mincuts span all mincut vectors. Because any proper, laminar, complement-free set family on $n$ elements has size at most $2n - 3$, the cut dimension cannot exceed $2n - 3$.
-
Graph Operations (Separation and Merge): Following cactus-representation techniques, they analyze non-star crossless cuts. Decomposing a graph $G$ along such a cut into smaller graphs $G_0$ and $G_1$ yields $\text{cdim}(G) \le \text{cdim}(G_0) + \text{cdim}(G_1) - 1$, with equality holding when the separating cut is connected.
-
$\ell_1$-Approximate Cut Dimension: To overcome the $2n - 3$ barrier, the authors formulate an adversary argument involving all cuts via linear programming duality. A cut of weight $\lambda + \delta$ can be perturbed by a non-negative vector $u$ whose weighted $\ell_1$-norm satisfies $\|u\|_{1,w} \le \delta$. The $\ell_1$-approximate cut dimension is defined as the minimum rank over all valid one-sided perturbations. They lower-bound this quantity using properties of strictly diagonally dominant matrices and direct unions of $K_4$ subgraphs.
Datasets
Not discussed in the paper (this is a purely theoretical paper; no empirical datasets were evaluated).
Key Insights and Ideas
- Cuts Have Low Algebraic Complexity: Even though an $n$-vertex graph can have up to $\binom{n}{2}$ distinct minimum cuts (achieved by the cycle graph $C_n$), their span cannot exceed $2n - 3$ dimensions.
- Exact Cut Dimension Cannot Beat $2n - 3$: Because the cut dimension is capped at $2n - 3$, adversary arguments relying purely on exact mincuts cannot prove query lower bounds larger than $2n - 3$.
- Near-Mincuts Differ Radially Between Simple and Weighted Graphs:
- For simple (unweighted) graphs, the span of $\alpha$-near mincuts (weight $\le \alpha \lambda$) remains $O(n)$ for any constant $\alpha < 2$. At $\alpha = 2$, it jumps to $\binom{n}{2}$.
- For weighted graphs, adding infinitesimal weights $\varepsilon$ breaks this property entirely: for any $\alpha > 1$, there exist graphs whose $\alpha$-near mincuts span the entire $\binom{n}{2}$-dimensional space. This demonstrates why a perturbation-based metric like the $\ell_1$-approximate cut dimension is necessary.
Key Results
- Cut Dimension Bounds: For every $n \ge 2$, $\text{cdim}(G) \le 2n - 3$, and there exist complete weighted graphs realizing $\text{cdim}(G) = 2n - 3$.
- Linear & Cut Query Lower Bound: Computing the minimum cut requires at least $2n - 3$ queries for any deterministic algorithm using cut or linear queries.
- Improved $2n - 2$ Lower Bound: By constructing a direct union of $k$ copies of $K_4$ on $n = 3k + 1$ vertices, the authors prove an $\ell_1$-approximate cut dimension of $6k = 2n - 2$. Consequently, any deterministic algorithm computing mincut requires at least $2n - 2$ linear queries.
- Symmetric Submodular Minimization: Because mincut is a special case of minimizing a symmetric submodular function, this establishes a new record lower bound of $2n - 2$ evaluation queries for finding a non-trivial minimum.
Limitations and Future Work
- Significant Complexity Gap: A large gap remains between the $2n - 2$ lower bound and the worst-case $\Omega(n^2 / \log n)$ upper bound achieved by learning the whole graph. The authors conjecture the existence of a deterministic cut-query algorithm running in $O(n^{2-\varepsilon})$ queries for some $\varepsilon > 0$.
- Upper Bounds on Approximate Cut Dimension: It remains open whether the $\ell_1$-approximate cut dimension is always $O(n)$ for general graphs.
- Direct Sum Theorems: The $2n - 2$ lower bound proof relies on explicit Gaussian elimination and diagonal dominance tailored to $K_4$; a general direct sum theorem for the $\ell_1$-approximate cut dimension remains unproven.
Summary updated