通过统计子图连通块数，高效重构图结构。
Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs
- 用子图连通块数量作为查询反馈，设计自适应重构算法。
- 期望只需 Θ(m log n / log m) 次查询即可完成重构。
- 适用于需要低查询成本的图学习与网络推断任务。
图重构问题在多种查询模型下被广泛研究。本文提出一种新查询模型：给定顶点子集，查询返回其诱导子图中的连通块数量。该问题旨在重建一个含 $n$ 个顶点、$m$ 条边的图。我们证明，在自适应条件下，期望 $Θ(\frac{m \log n}{\log m})$ 次查询既充分又必要。相比之下，即使 $m = O(n)$，非自适应查询仍需 $Ω(n^2)$ 次。此外，我们给出一个仅需两轮自适应、总查询次数为 $O(m\log n + n\log^2 n)$ 的算法。
原文摘要 · Abstract (English)
The graph reconstruction problem has been extensively studied under various query models. In this paper, we propose a new query model regarding the number of connected components, which is one of the most basic and fundamental graph parameters. Formally, we consider the problem of reconstructing an $n$-node $m$-edge graph with oracle queries of the following form: provided with a subset of vertices, the oracle returns the number of connected components in the induced subgraph. We show $Θ(\frac{m \log n}{\log m})$ queries in expectation are both sufficient and necessary to adaptively reconstruct the graph. In contrast, we show that $Ω(n^2)$ non-adaptive queries are required, even when $m = O(n)$. We also provide an $O(m\log n + n\log^2 n)$ query algorithm using only two rounds of adaptivity.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。