DROPS

Document

DOI: 10.4230/LIPIcs.WG.2026.24

Graph Reconstruction with a Connected Components Oracle

Authors: Juha Harviainen and Pekka Parviainen

Published in: LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)

Abstract

In the Graph Reconstruction (GR) problem, the goal is to recover a hidden graph by utilizing some oracle that provides limited access to the structure of the graph. The interest is in characterizing how strong different oracles are when the complexity of an algorithm is measured in the number of performed queries. We study a novel oracle that returns the set of connected components (CC) on the subgraph induced by the queried subset of vertices. Our main contributions are as follows: 1) For a hidden graph with n vertices, m edges, maximum degree Δ, and treewidth k, GR can be solved in 𝒪(min{m/log m, Δ², k²} ⋅ log n) CC queries by an adaptive randomized algorithm. 2) For a hidden graph with n vertices and degeneracy d, GR can be solved in 𝒪(d² log² n) CC queries by an adaptive randomized algorithm. 3) There are hidden graphs with n vertices, m edges, maximum degree Δ, treewidth k, and degeneracy d such that Ω(m), Ω(Δ²), Ω(k²), and Ω(d²) CC queries are required for solving GR.

Cite as

Juha Harviainen and Pekka Parviainen. Graph Reconstruction with a Connected Components Oracle. In 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 376, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{harviainen_et_al:LIPIcs.WG.2026.24,
  author =	{Harviainen, Juha and Parviainen, Pekka},
  title =	{{Graph Reconstruction with a Connected Components Oracle}},
  booktitle =	{52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)},
  pages =	{24:1--24:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-430-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{376},
  editor =	{Goedgebeur, Jan and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.24},
  URN =		{urn:nbn:de:0030-drops-261907},
  doi =		{10.4230/LIPIcs.WG.2026.24},
  annote =	{Keywords: graph reconstruction, parameterized complexity, query complexity}
}

Search Results

Documents authored by Harviainen, Juha

Graph Reconstruction with a Connected Components Oracle

Abstract

Cite as

Thanks for your feedback!

Could not send message