Complexity of learning matchings and half graphs via edge queries
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911038453055488 |
|---|---|
| author | Mande, Nikhil S. Sanyal, Swagato Zamaraev, Viktor |
| author_facet | Mande, Nikhil S. Sanyal, Swagato Zamaraev, Viktor |
| contents | The problem of learning or reconstructing an unknown graph from a known family via partial-information queries arises as a mathematical model in various contexts. The most basic type of access to the graph is via \emph{edge queries}, where an algorithm may query the presence/absence of an edge between a pair of vertices of its choosing, at unit cost.
While more powerful query models have been extensively studied in the context of graph reconstruction, the basic model of edge queries seems to have not attracted as much attention. In this paper we study the edge query complexity of learning a hidden bipartite graph, or equivalently its bipartite adjacency matrix, in the classical as well as quantum settings. We focus on learning matchings and half graphs, which are graphs whose bipartite adjacency matrices are a row/column permutation of the identity matrix and the lower triangular matrix with all entries on and below the principal diagonal being 1, respectively.
\begin{itemize}
\item For matchings of size $n$, we show a tight deterministic bound of $n(n-1)/2$ and an asymptotically tight randomized bound of $Θ(n^2)$. A quantum bound of $Θ(n^{1.5})$ was shown in a recent work of van Apeldoorn et al.~[ICALP'21].
\item For half graphs whose bipartite adjacency matrix is a column-permutation of the $n \times n$ lower triangular matrix,
we give tight $Θ(n \log n)$ bounds in both deterministic and randomized settings, and an $Ω(n)$ quantum lower bound. \item For general half graphs,
we observe that the problem is equivalent to a natural generalization of the famous nuts-and-bolts problem, leading to a tight $Θ(n \log n)$ randomized bound.
We also present a simple quicksort-style method that instantiates to a $O(n \log^2 n)$ randomized algorithm and a tight $O(n \log n)$ quantum algorithm.
\end{itemize} |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_03151 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Complexity of learning matchings and half graphs via edge queries Mande, Nikhil S. Sanyal, Swagato Zamaraev, Viktor Computational Complexity Discrete Mathematics Combinatorics 68Q04, 68Q12 The problem of learning or reconstructing an unknown graph from a known family via partial-information queries arises as a mathematical model in various contexts. The most basic type of access to the graph is via \emph{edge queries}, where an algorithm may query the presence/absence of an edge between a pair of vertices of its choosing, at unit cost. While more powerful query models have been extensively studied in the context of graph reconstruction, the basic model of edge queries seems to have not attracted as much attention. In this paper we study the edge query complexity of learning a hidden bipartite graph, or equivalently its bipartite adjacency matrix, in the classical as well as quantum settings. We focus on learning matchings and half graphs, which are graphs whose bipartite adjacency matrices are a row/column permutation of the identity matrix and the lower triangular matrix with all entries on and below the principal diagonal being 1, respectively. \begin{itemize} \item For matchings of size $n$, we show a tight deterministic bound of $n(n-1)/2$ and an asymptotically tight randomized bound of $Θ(n^2)$. A quantum bound of $Θ(n^{1.5})$ was shown in a recent work of van Apeldoorn et al.~[ICALP'21]. \item For half graphs whose bipartite adjacency matrix is a column-permutation of the $n \times n$ lower triangular matrix, we give tight $Θ(n \log n)$ bounds in both deterministic and randomized settings, and an $Ω(n)$ quantum lower bound. \item For general half graphs, we observe that the problem is equivalent to a natural generalization of the famous nuts-and-bolts problem, leading to a tight $Θ(n \log n)$ randomized bound. We also present a simple quicksort-style method that instantiates to a $O(n \log^2 n)$ randomized algorithm and a tight $O(n \log n)$ quantum algorithm. \end{itemize} |
| title | Complexity of learning matchings and half graphs via edge queries |
| topic | Computational Complexity Discrete Mathematics Combinatorics 68Q04, 68Q12 |
| url | https://arxiv.org/abs/2507.03151 |