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.
In the above image, we can see that all pairs from the left vertex set are connected to each other via one from the other set. Now from the image it is seen that for a pair, there can be multiple paths eg : (3,4) "looks like " it is connected via 6 as well as 7. But the pair (3, 4) was allocated to 6 and not 7. The edge 3-7 and 4-7 simply exist because of other pairs like (2, 3) and (2, 4) that were allocated to 7. Sorry for the poor explanation.
One possibility is to solve this as a balanced transportation problem. Here I assume $K$ is even, since for every edge entering a node in $V_2$, there must be an edge leaving a node in $V_2$. Let $S=V_1\times{V_1}$ (i.e. the set of all pairs of nodes in $V_1$). Each node in $S$ has a supply of $1$. In addition, add a dummy supply node $s_0$ with supply $\tfrac{1}{2}|V_2|K-|V_1|^2$ (which I assume is positive, or your problem is infeasible). The set of demand nodes is $V_2$, each with demand $K/2$. For each $(i,j)\in{S}$ and $k\in{V_2}$, the cost to ship from $(i,j)$ to $k$ is $\operatorname{dist}(i,k)+\operatorname{dist}(j,k)$. For all $k\in{V_2}$, the cost to ship from $s_0$ to $k$ is $0$.
Assuming the distances are integral (which can be accomplished to arbitrary approximation accuracy with scaling), this balanced transportation problem will provide an optimal solution to your problem in polynomial time (and is quite efficient in practice).