On the cut dimension of a graph
Preprint
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.
Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- A Note on a Recent Algorithm for Minimum Cut2021
- Local Flow Partitioning for Faster Edge ConnectivitySIAM Journal on Computing, 2020
- Deterministic Edge Connectivity in Near-Linear TimeJournal of the ACM, 2018
- On the Number of Minimum Cuts in a GraphSIAM Journal on Discrete Mathematics, 2004
- A Factor 2 Approximation Algorithm for the Generalized Steiner Network ProblemCombinatorica, 2001
- Minimum cuts in near-linear timeJournal of the ACM, 2000
- Computing All Small Cuts in an Undirected NetworkSIAM Journal on Discrete Mathematics, 1997
- On the number of small cuts in a graphInformation Processing Letters, 1996
- The Minimum Number of Edges and Vertices in a Graph with Edge Connectivity n and m n‐BondsNetworks, 1975
- Graph Connectivity and Single Element Recovery via Linear and OR Queries