Exact Learning of Weighted Graphs Using Composite Queries
By: Michael T. Goodrich, Songyu Liu, Ioannis Panageas
Potential Business Impact:
Finds hidden connections in networks using smart questions.
In this paper, we study the exact learning problem for weighted graphs, where we are given the vertex set, $V$, of a weighted graph, $G=(V,E,w)$, but we are not given $E$. The problem, which is also known as graph reconstruction, is to determine all the edges of $E$, including their weights, by asking queries about $G$ from an oracle. As we observe, using simple shortest-path length queries is not sufficient, in general, to learn a weighted graph. So we study a number of scenarios where it is possible to learn $G$ using a subquadratic number of composite queries, which combine two or three simple queries.
Similar Papers
Approximating the Average-Case Graph Search Problem with Non-Uniform Costs
Data Structures and Algorithms
Finds hidden things in networks faster.
Weighted $k$-Path and Other Problems in Almost $O^*(2^k)$ Deterministic Time via Dynamic Representative Sets
Data Structures and Algorithms
Finds shortest paths with many stops faster.
Optimal non-adaptive algorithm for edge estimation
Data Structures and Algorithms
Counts graph connections with few guesses.