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 ≥ 2 we show that the cut dimension of an nvertex graph is at most 2n3, and construct graphs realizing this bound.
The cut dimension was recently defined by Graur et al. [Andrei Graur et al., 2020], who show that the maximum cut dimension of an nvertex graph is a lower bound on the number of cut queries needed by a deterministic algorithm to solve the minimum cut problem on nvertex 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 ∈ ℝ^{binom(n,2)} and receives the answer w^T x. Our results thus show a lower bound of 2n3 on the number of linear queries needed by a deterministic algorithm to solve minimum cut on nvertex 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 𝓁₁approximate cut dimension. The 𝓁₁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 𝓁₁approximate cut dimension 2n2, showing that it can be strictly larger than the cut dimension.
BibTeX  Entry
@InProceedings{lee_et_al:LIPIcs.CCC.2021.15,
author = {Lee, Troy and Li, Tongyang and Santha, Miklos and Zhang, Shengyu},
title = {{On the Cut Dimension of a Graph}},
booktitle = {36th Computational Complexity Conference (CCC 2021)},
pages = {15:115:35},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771931},
ISSN = {18688969},
year = {2021},
volume = {200},
editor = {Kabanets, Valentine},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14289},
URN = {urn:nbn:de:0030drops142890},
doi = {10.4230/LIPIcs.CCC.2021.15},
annote = {Keywords: Query complexity, submodular function minimization, cut dimension}
}
Keywords: 

Query complexity, submodular function minimization, cut dimension 
Collection: 

36th Computational Complexity Conference (CCC 2021) 
Issue Date: 

2021 
Date of publication: 

08.07.2021 