RECORD
Learning Spanning Forests Optimally using CUT Queries in Weighted Undirected Graphs
Data Structures and Algorithms · Submitted 16 Jun 2023
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim In this paper we describe a randomized algorithm which returns a maximal spanning forest of an unknown {\em weighted} undirected graph making $O(n)$ $\mathsf{CUT}$ queries in expectation.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
In this paper we describe a randomized algorithm which returns a maximal spanning forest of an unknown {\em weighted} undirected graph making $O(n)$ $\mathsf{CUT}$ queries in expectation. For weighted graphs, this is optimal due to a result in [Auza and Lee, 2021] which shows an $\Omega(n)$ lower bound for zero-error randomized algorithms. %To our knowledge, it is the only regime of this problem where we have upper and lower bounds tight up to constants. These questions have been extensively studied in the past few years, especially due to the problem's connections to symmetric submodular function minimization. We also describe a simple polynomial time deterministic algorithm that makes $O(\frac{n\log n}{\log\log n})$ queries on undirected unweighted graphs and returns a maximal spanning forest, thereby (slightly) improving upon the state-of-the-art.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | In this paper we describe a randomized algorithm which returns a maximal spanning forest of an unknown {\em weighted} undirected graph making $O(n)$ $\mathsf{CUT}$ queries in expectation. | contribution 0.93 | 0.95 | 0.83 | asserted 1.00 |
| s1 | For weighted graphs, this is optimal due to a result in [Auza and Lee, 2021] which shows an $\Omega(n)$ lower bound for zero-error randomized algorithms. %To our knowledge, it is the only regime of this problem where we have upper and lower bounds tight up to constants. | interpretation 0.85 | 0.13 | 0.34 | asserted 1.00 |
| s2 | These questions have been extensively studied in the past few years, especially due to the problem's connections to symmetric submodular function minimization. | background 1.00 | 0.04 | 0.02 | asserted 1.00 |
| s3 | We also describe a simple polynomial time deterministic algorithm that makes $O(\frac{n\log n}{\log\log n})$ queries on undirected unweighted graphs and returns a maximal spanning forest, thereby (slightly) improving upon the state-of-the-art. | contribution 0.93 | 0.96 | 0.11 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
In this paper we describe a randomized algorithm which returns a maximal spanning forest of an unknown {\em weighted} undirected graph making $O(n)$ $\mathsf{CUT}$ queries in expectation. For weighted graphs, this is optimal due to a result in [Auza and Lee, 2021] which shows an $\Omega(n)$ lower bound for zero-error randomized algorithms. %To our knowledge, it is the only regime of this problem where we have upper and lower bounds tight up to constants. These questions have been extensively studied in the past few years, especially due to the problem's connections to symmetric submodular function minimization. We also describe a simple polynomial time deterministic algorithm that makes $O(\frac{n\log n}{\log\log n})$ queries on undirected unweighted graphs and returns a maximal spanning forest, thereby (slightly) improving upon the state-of-the-art.
Human review
How the literature uses it
What this paper does with the arXiv papers it cites
What it cites · 1 sentence without a confident label
Compares with 1 paper
-
It also closes the gap between the lower bound result of $Ω(n)$ in [ref] and previous upper bound of $O(n logn)$.
On the query complexity of connectivity with global queries · Conclusion · 0.96
Cites as background 1 paper
-
This particular question of connectivity has seen a lot of interest in the recent years (cf. [ref] ) mainly due to the connections to streaming and sketching, but also due to connections to submodular function minimization (SFM).
On the query complexity of connectivity with global queries · Introduction · 0.96
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.