Given two vertex sets $V_1$ and $V_2$. The vertices in $V_2$ have a limitation on the maximum degree of each vertex being $K$. I need to find an allocation algorithm such that every pair of vertices in $V_1$ is interconnected via a vertex in $V_2$ i.e $X \leftrightarrow Y \leftrightarrow Z$ , where $X,Z \in V_1$ and $Y \in V_2$.
The goal is to find an allocation that minimizes the distances between all such pairs in $V_1$. The distance is measured as : $\; dist(X, Y) + dist(Y, Z)\;$. The distances are provided beforehand. I kind of came up with an algorithm, but it doesn't guarantee optimality. Any help will be appreciated.