论文标题
在图表的剪切尺寸上
On the cut dimension of a graph
论文作者
论文摘要
令$ g =（v，w）$是带有$ m $边缘的加权无向图。 $ g $的剪切尺寸是$ g $的最小切割的特征向量的跨度，被视为$ \ {0,1 \}^m $中的向量。对于每$ n \ ge 2 $，我们都会显示$ n $ vertex图的剪切尺寸最多为$ 2N-3 $，并且构造图表实现了这种界限。 切割维度最近由Graur等人定义。 Graur等人的每$ n \ ge 2 $，在带有切割尺寸的$ N $顶点上的图表至少$ 3N/2 -2 -2 $，从而在确定性切割的查询复杂性的计算机Mincut中提供了第一个下限大于$ n $。我们观察到，剪切维度甚至是确定性算法所需的\ emph {linear}查询数量的下限。因此，我们的结果表明，确定性算法所需的线性查询数量为$ 2N-3 $，以解决在$ n $ vertex图上求解最小值的最低限度，这意味着一个人不能通过切割尺寸显示出比此限制的下限。 我们进一步介绍了切割维度的概括，我们称之为$ \ ell_1 $ - approximate cut维度。 $ \ ell_1 $ -Appro-Approximate Cut维度也是确定性算法所需的线性查询数量的下限，以计算最小值。它总是至少与切割维度一样大，我们在$ n = 3k+1 $的顶点上构建了一个无限的图形家族，带有$ \ ell_1 $ -approximate cut Dimension $ 2N-2 $，表明它可能大于切割尺寸。
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.
