Learning Spanning Forests Optimally in Weighted Undirected Graphs with CUT Queries
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. 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.
Cite
Text
Liao and Chakrabarty. "Learning Spanning Forests Optimally in Weighted Undirected Graphs with CUT Queries." Proceedings of The 35th International Conference on Algorithmic Learning Theory, 2024.Markdown
[Liao and Chakrabarty. "Learning Spanning Forests Optimally in Weighted Undirected Graphs with CUT Queries." Proceedings of The 35th International Conference on Algorithmic Learning Theory, 2024.](https://mlanthology.org/alt/2024/liao2024alt-learning/)BibTeX
@inproceedings{liao2024alt-learning,
title = {{Learning Spanning Forests Optimally in Weighted Undirected Graphs with CUT Queries}},
author = {Liao, Hang and Chakrabarty, Deeparnab},
booktitle = {Proceedings of The 35th International Conference on Algorithmic Learning Theory},
year = {2024},
pages = {785-807},
volume = {237},
url = {https://mlanthology.org/alt/2024/liao2024alt-learning/}
}