Query Complexity of the Metric Steiner Tree Problem

Yu Chen, Sanjeev Khanna, Zihan Tan

We study the query complexity of the metric Steiner Tree problem, where we are given an $n\times n$ metric on a set $V$ of vertices along with a set $T\subseteq V$ of $k$ termina…