A Query Algorithm for Learning a Spanning Forest in Weighted Undirected Graphs

Deeparnab Chakrabarty, Hang Liao
Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:259-274, 2023.

Abstract

We consider the problem of finding a spanning forest in an unknown {\em weighted} undirected graph when the access to the graph is via CUT queries, that is, one can query a subset S⊆V of vertices and get the cut-value ∑e∈∂Sw(e) as the response. It is not too hard to solve this problem using O(nlogn) queries mimicking a Prim-style algorithm using a binary-search style idea. In this paper we use the power of CUT queries to obtain a Monte-Carlo algorithm that makes O(nloglogn(logloglogn)2) CUT queries. At the core of our contribution is a generalization of a result in [Apers et al., 2022] which studies the same problem on unweighted graphs, but to handle weights, we need to combine their ideas with ideas for {\em support estimation} of weighted vectors, as in [Stockmeyer, 1983], and {\em weighted graph reconstruction} algorithms, as in [Bshouty and Mazzawi, 2012].

Cite this Paper

BibTeX
@InProceedings{pmlr-v201-chakrabarty23a, title = {A Query Algorithm for Learning a Spanning Forest in Weighted Undirected Graphs}, author = {Chakrabarty, Deeparnab and Liao, Hang}, booktitle = {Proceedings of The 34th International Conference on Algorithmic Learning Theory}, pages = {259--274}, year = {2023}, editor = {Agrawal, Shipra and Orabona, Francesco}, volume = {201}, series = {Proceedings of Machine Learning Research}, month = {20 Feb--23 Feb}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v201/chakrabarty23a/chakrabarty23a.pdf}, url = {https://proceedings.mlr.press/v201/chakrabarty23a.html}, abstract = {We consider the problem of finding a spanning forest in an unknown {\em weighted} undirected graph when the access to the graph is via CUT queries, that is, one can query a subset $S\subseteq V$ of vertices and get the cut-value $\sum_{e\in \partial S} w(e)$ as the response. It is not too hard to solve this problem using $O(n\log n)$ queries mimicking a Prim-style algorithm using a binary-search style idea. In this paper we use the power of CUT queries to obtain a Monte-Carlo algorithm that makes $O(n\log \log n(\log\log\log n)^2)$ CUT queries. At the core of our contribution is a generalization of a result in [Apers et al., 2022] which studies the same problem on unweighted graphs, but to handle weights, we need to combine their ideas with ideas for {\em support estimation} of weighted vectors, as in [Stockmeyer, 1983], and {\em weighted graph reconstruction} algorithms, as in [Bshouty and Mazzawi, 2012]. } }
Endnote
%0 Conference Paper %T A Query Algorithm for Learning a Spanning Forest in Weighted Undirected Graphs %A Deeparnab Chakrabarty %A Hang Liao %B Proceedings of The 34th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Shipra Agrawal %E Francesco Orabona %F pmlr-v201-chakrabarty23a %I PMLR %P 259--274 %U https://proceedings.mlr.press/v201/chakrabarty23a.html %V 201 %X We consider the problem of finding a spanning forest in an unknown {\em weighted} undirected graph when the access to the graph is via CUT queries, that is, one can query a subset $S\subseteq V$ of vertices and get the cut-value $\sum_{e\in \partial S} w(e)$ as the response. It is not too hard to solve this problem using $O(n\log n)$ queries mimicking a Prim-style algorithm using a binary-search style idea. In this paper we use the power of CUT queries to obtain a Monte-Carlo algorithm that makes $O(n\log \log n(\log\log\log n)^2)$ CUT queries. At the core of our contribution is a generalization of a result in [Apers et al., 2022] which studies the same problem on unweighted graphs, but to handle weights, we need to combine their ideas with ideas for {\em support estimation} of weighted vectors, as in [Stockmeyer, 1983], and {\em weighted graph reconstruction} algorithms, as in [Bshouty and Mazzawi, 2012].
APA
Chakrabarty, D. & Liao, H.. (2023). A Query Algorithm for Learning a Spanning Forest in Weighted Undirected Graphs. Proceedings of The 34th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 201:259-274 Available from https://proceedings.mlr.press/v201/chakrabarty23a.html.

Related Material