On the cut dimension of a graph

Troy Lee, Tongyang Li, Miklos Santha, Shengyu Zhang

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

  1. 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.
  2. 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.
  3. 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

Abstract

Let $G = (V,w)$ be a weighted undirected graph with $m$ edges. The cut dimension of $G$ is the dimension of the span of the characteristic vectors of the minimum cuts of $G$, viewed as vectors in $\{0,1\}^m$. For every $n \ge 2$ we show that the cut dimension of an $n$-vertex graph is at most $2n-3$, and construct graphs realizing this bound. The cut dimension was recently defined by Graur et al.\ \cite{GPRW20}, who show that the maximum cut dimension of an $n$-vertex graph is a lower bound on the number of cut queries needed by a deterministic algorithm to solve the minimum cut problem on $n$-vertex graphs. For every $n\ge 2$, Graur et al.\ exhibit a graph on $n$ vertices with cut dimension at least $3n/2 -2$, giving the first lower bound larger than $n$ on the deterministic cut query complexity of computing mincut. We observe that the cut dimension is even a lower bound on the number of \emph{linear} queries needed by a deterministic algorithm to solve mincut, where a linear query can ask any vector $x \in \mathbb{R}^{\binom{n}{2}}$ and receives the answer $w^T x$. Our results thus show a lower bound of $2n-3$ on the number of linear queries needed by a deterministic algorithm to solve minimum cut on $n$-vertex graphs, and imply that one cannot show a lower bound larger than this via the cut dimension. We further introduce a generalization of the cut dimension which we call the $\ell_1$-approximate cut dimension. The $\ell_1$-approximate cut dimension is also a lower bound on the number of linear queries needed by a deterministic algorithm to compute minimum cut. It is always at least as large as the cut dimension, and we construct an infinite family of graphs on $n=3k+1$ vertices with $\ell_1$-approximate cut dimension $2n-2$, showing that it can be strictly larger than the cut dimension.
BibTeX
@inproceedings{lee2021cut,
  author = {Troy Lee and Tongyang Li and Miklos Santha and Shengyu Zhang},
  title = {{On the cut dimension of a graph}},
  booktitle = {CCC},
  year = {2021},
  url = {https://openreview.net/forum?id=6wuMx4Wjkyc},
}

Loading related content...

Figure