2026-07-21T23:54:36Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:14289 2024-03-06T10:53:53Z ddc:004 open_access
On the Cut Dimension of a Graph Lee, Troy Li, Tongyang Santha, Miklos Zhang, Shengyu Query complexity submodular function minimization cut dimension 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. [Andrei Graur et al., 2020], 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 ∈ ℝ^{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 𝓁₁-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 2n-2, showing that it can be strictly larger than the cut dimension. Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Troy Lee and Tongyang Li and Miklos Santha and Shengyu Zhang 2021 Is Part Of LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2021.15 urn:nbn:de:0030-drops-142890 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.15 eng https://creativecommons.org/licenses/by/4.0/legalcode