On the cut dimension of a graph
On the cut dimension of a graph
复制标题
关于图的割维
DOI：
10.4230/lipics.ccc.2021.15
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Shengyu Zhang
中科院分区：
文献类型：
--
作者：
Troy Lee;Tongyang Li;M. Santha;Shengyu Zhang
设G = (V, w)是一个有m条边的加权无向图。G的切维是G的最小切维的特征向量张成的维数，看作是{0,1}m中的向量。对于每一个n≥2，我们证明了n顶点图的切维不超过2n−3，并构造了实现这一界的图。割维最近由Graur等人定义，他们表明n顶点图的最大割维是确定性算法解决n顶点图的最小割问题所需的切查询次数的下界。对于每一个n≥2，Graur等人给出了一个包含n个顶点且切维至少为3n/2−2的图，给出了计算最小切的确定性切查询复杂度大于n的第一个下界。我们观察到削减维甚至一个下界的数量线性查询所需的确定性算法解决mincut,线性查询可以问任何向量x∈R (n2)和接收答案wT x。因此我们的结果显示一个下界的2 n−3的数量线性查询所需的确定性算法解决最低减少n点图表,意味着一个人不能显示一个下界通过减少大于这个维度。我们进一步引入了切维的一般化，我们称之为1-近似切维。1-近似切维也是确定性算法计算最小切维所需的线性查询数的下界。它总是至少和切维一样大，并且我们构造了一个无限族图，在n = 3k + 1个顶点上，具有1-近似切维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 ≥ 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. [13], 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 ≥ 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 linear queries needed by a deterministic algorithm to solve mincut, where a linear query can ask any vector x ∈ R(n2) and receives the answer wT 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 ℓ1-approximate cut dimension. The ℓ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 ℓ1-approximate cut dimension 2n − 2, showing that it can be strictly larger than the cut dimension.
DOI：
10.4230/lipics.esa.2021.7
发表时间：
2020-07
期刊：
--
影响因子：
--
作者：
Sepehr Assadi;Deeparnab Chakrabarty;S. Khanna
通讯作者：
Sepehr Assadi;Deeparnab Chakrabarty;S. Khanna