Query-decision Regression between Shortest Path and Minimum Steiner Tree

Guangmo Tong, Peng Zhao, Mina Samizadeh

Considering a graph with unknown weights, can we find the shortest path for a pair of nodes if we know the minimal Steiner trees associated with some subset of nodes? That is, with…