Quasi-linear distance query reconstruction for graphs of bounded treelength
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916442047250432 |
|---|---|
| author | Bastide, Paul Groenland, Carla |
| author_facet | Bastide, Paul Groenland, Carla |
| contents | In distance query reconstruction, we wish to reconstruct the edge set of a hidden graph by asking as few distance queries as possible to an oracle. Given two vertices $u$ and $v$, the oracle returns the shortest path distance between $u$ and $v$ in the graph.
The length of a tree decomposition is the maximum distance between two vertices contained in the same bag. The treelength of a graph is defined as the minimum length of a tree decomposition of this graph. We present an algorithm to reconstruct an $n$-vertex connected graph $G$ parameterized by maximum degree $Δ$ and treelength $k$ in $O_{k,Δ}(n \log^2 n)$ queries (in expectation). This is the first algorithm to achieve quasi-linear complexity for this class of graphs. The proof goes through a new lemma that could give independent insight on graphs of bounded treelength. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_12594 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quasi-linear distance query reconstruction for graphs of bounded treelength Bastide, Paul Groenland, Carla Data Structures and Algorithms Discrete Mathematics Combinatorics In distance query reconstruction, we wish to reconstruct the edge set of a hidden graph by asking as few distance queries as possible to an oracle. Given two vertices $u$ and $v$, the oracle returns the shortest path distance between $u$ and $v$ in the graph. The length of a tree decomposition is the maximum distance between two vertices contained in the same bag. The treelength of a graph is defined as the minimum length of a tree decomposition of this graph. We present an algorithm to reconstruct an $n$-vertex connected graph $G$ parameterized by maximum degree $Δ$ and treelength $k$ in $O_{k,Δ}(n \log^2 n)$ queries (in expectation). This is the first algorithm to achieve quasi-linear complexity for this class of graphs. The proof goes through a new lemma that could give independent insight on graphs of bounded treelength. |
| title | Quasi-linear distance query reconstruction for graphs of bounded treelength |
| topic | Data Structures and Algorithms Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2410.12594 |