Learning Spanning Forests Optimally in Weighted Undirected Graphs with CUT queries

Hang Liao, Deeparnab Chakrabarty
Proceedings of The 35th International Conference on Algorithmic Learning Theory, PMLR 237:785-807, 2024.

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 this Paper

BibTeX
@InProceedings{pmlr-v237-liao24b, 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}, pages = {785--807}, year = {2024}, editor = {Vernade, Claire and Hsu, Daniel}, volume = {237}, series = {Proceedings of Machine Learning Research}, month = {25--28 Feb}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v237/liao24b/liao24b.pdf}, url = {https://proceedings.mlr.press/v237/liao24b.html}, 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.} }
Endnote
%0 Conference Paper %T Learning Spanning Forests Optimally in Weighted Undirected Graphs with CUT queries %A Hang Liao %A Deeparnab Chakrabarty %B Proceedings of The 35th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2024 %E Claire Vernade %E Daniel Hsu %F pmlr-v237-liao24b %I PMLR %P 785--807 %U https://proceedings.mlr.press/v237/liao24b.html %V 237 %X 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.
APA
Liao, H. & Chakrabarty, D.. (2024). Learning Spanning Forests Optimally in Weighted Undirected Graphs with CUT queries. Proceedings of The 35th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 237:785-807 Available from https://proceedings.mlr.press/v237/liao24b.html.

Related Material