Abstract
In the study of graph algorithms, the "cut dimension" of a graph $G$ is defined as the dimension of the span of the characteristic vectors of its minimum cuts. This paper establishes that for any $n$-vertex weighted undirected graph, the cut dimension is at most $2n-3$. This result provides a fundamental limit on the lower bounds that can be proven for the deterministic query complexity of the minimum cut problem using this technique. Furthermore, the authors introduce the $\ell_1$-approximate cut dimension, a generalization that yields a higher lower bound of $2n-2$ for linear queries, narrowing the gap in our understanding of the computational limits of finding minimum cuts.
Introduction
The minimum cut (min-cut) problem is a cornerstone of combinatorial optimization. While efficient randomized algorithms exist to find the minimum set of edges that disconnects a graph, the deterministic query complexity—the number of questions an algorithm must ask about edge weights to identify the min-cut—remains an area of active research.
Recent work by Graur et al. (2020) introduced the cut dimension as a tool to establish lower bounds on this complexity. If an algorithm asks for the weights of specific cuts, the number of queries must at least match the dimension of the space spanned by the min-cuts' characteristic vectors. This paper refines this theory, providing tight bounds and extending the model to more powerful "linear queries."
The Cut Dimension: A Structural Limit
The primary contribution of this work is the proof that the cut dimension of an $n$-vertex graph is at most $2n-3$. This is a significant improvement over previous bounds and is shown to be tight through explicit graph constructions.
Combinatorial Uncrossing and Cactus Representations
To arrive at the $2n-3$ bound, the authors utilize the principle of combinatorial uncrossing. In graph theory, if two min-cuts "cross" (sharing vertices in a specific overlapping pattern), they can be transformed into two other cuts that do not cross. This structural property implies that any maximal set of linearly independent min-cuts can be represented in a way that limits their total number.
This relates closely to the cactus representation of a graph. A cactus graph is a structure that compactly represents all min-cuts of a given graph. The authors demonstrate that the cut dimension is essentially a measure of the complexity of this cactus structure. By performing induction on graph operations—specifically "separations" (decomposing a graph along a cut) and "merges" (joining graphs at a vertex)—they prove that the linear independence of these cuts cannot exceed the $2n-3$ threshold.
Linear Queries and the $\ell_1$-Approximate Cut Dimension
The paper goes beyond standard cut queries to consider linear queries. In this model, an algorithm can ask for the weighted sum of any set of edges, not just those forming a cut. This is a much more powerful query model, yet the authors show that the cut dimension still serves as a lower bound.
However, the standard cut dimension has its limits. To push the lower bound further, the authors introduce the $\ell_1$-approximate cut dimension. This concept considers not just the exact min-cuts, but the space of vectors that are "close" to the min-cuts in an $\ell_1$ sense.
Key Findings in Query Complexity
- Tightness of Cut Dimension: The authors construct specific graphs that achieve a cut dimension of exactly $2n-3$, proving their upper bound cannot be lowered further.
- The $2n-2$ Bound: By applying the $\ell_1$-approximate cut dimension to a construction involving the direct union of $K_4$ (complete graphs on four vertices), the authors prove a lower bound of $2n-2$ for linear queries. This shows that the approximate version is a strictly more powerful tool for proving complexity limits than the standard cut dimension.
- Submodular Minimization: Since the cut function is a symmetric submodular function, these results translate directly to the broader field of submodular function minimization, providing the best-known lower bounds for that class of problems.
Discussion and Future Work
While this paper successfully establishes a $2n-3$ limit for the cut dimension, a significant gap remains in the field. The number of queries required to fully "learn" a graph is $O(n^2)$, yet the lower bounds proven here are linear ($O(n)$).
The authors conjecture that the true query complexity of the min-cut problem may be closer to quadratic, but they have effectively proven that the "cut dimension" technique cannot be used to show any bound higher than $2n-3$. Future research may need to develop entirely new algebraic or combinatorial tools to bridge this gap. Additionally, the complexity of randomized query algorithms remains an open question, as the current lower bounds apply only to deterministic approaches.
Summary updated