用有效电阻查询高效推断图结构特性，突破传统方法局限。
Graph Inference with Effective Resistance Queries
- 基于有效电阻查询设计新型图推断算法，实现高效属性检测。
- 提出多项式时间算法，仅需O(n)次查询即可验证树结构或割点等性质。
- 首次揭示有效电阻与最短路径查询模型不可比较，拓展图推理边界。
图推断旨在设计算法，通过查询隐藏图的预言机来学习其性质。图重构、验证与性质测试均属此类。本文研究使用返回顶点对间有效电阻（ER）的预言机进行图推断。尽管已知含n个顶点的图可通过所有\binom{n}{2}种可能的ER查询唯一重建，但相关研究仍十分有限。本文填补该空白，提出多项新结果：1. 基于$O(n)$次查询的算法，用于测试图是否为树、判断两图相等（假设一图为另一子图）、检测顶点或边是否为割点或割边；2. 性质测试算法，包括顶点/边双连通性测试，并给出从有界度模型到ER查询模型的归约，从而获得$ k $-连通性、二分性、平面性及固定子图包含性的ER查询算法；3. 图重构算法，包括基于低宽度树分解的重构方法，一个$Θ(k^2)$查询、多项式时间的算法以恢复被删除k个条目的邻接矩阵$A$，以及一个$ k $-查询、指数时间的相同任务算法。最后，我们比较了ER查询与最短路径查询的性能，发现二者在能力上不可比较。
原文摘要 · Abstract (English)
The goal of graph inference is to design algorithms for learning properties of a hidden graph using queries to an oracle that returns information about the graph. Graph reconstruction, verification, and property testing are all types of graph inference. In this work, we study graph inference using an oracle that returns the effective resistance (ER) between a pair of vertices. Effective resistance is a distance originating from the study of electrical circuits with many applications. However, ER has received little attention from a graph inference perspective. Indeed, although it is known that an $n$-vertex graph can be uniquely reconstructed from all $\binom{n}{2}$ possible ER queries, little else is known. We address this gap with several new results, including: 1. $O(n)$-query algorithms for testing whether a graph is a tree; deciding whether two graphs are equal assuming one is a subgraph of the other; and testing whether a given vertex (or edge) is a cut vertex (or cut edge). 2. Property testing algorithms, including for testing whether a graph is vertex- or edge-biconnected. We also give a reduction to adapt property testing results from the bounded-degree model to our ER query model. This yields ER-query-based algorithms for testing $k$-connectivity, bipartiteness, planarity, and containment of a fixed subgraph. 3. Graph reconstruction algorithms, including an algorithm for reconstructing a graph from a low-width tree decomposition; a $Θ(k^2)$-query, polynomial-time algorithm for recovering the adjacency matrix $A$ of a hidden graph, given $A$ with $k$ of its entries deleted; and a $k$-query, exponential-time algorithm for the same task. We also compare the power of ER queries and shortest path queries, which are closely related but better studied. Interestingly, we show that the two query models are incomparable in power.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。