I am trying to solve the problem below. It is like k-minimum-spanning-tree and the steiner tree problem, but it is with a graph.
- We have a non-negative undirected weighted graph G = (V, E).
- For every pair of vertices v1 and v2 there exists an edge e12. In other words, every vertex is connected to every other vertex.
- We shall create a subset of the vertices U that contains k vertices.
- Our goal is to select the n vertices in U such that the sum of the edges from each vertex in U to every other vertex is minimized. In other words, we want to select the vertices in U so that the sum of all the edges from the nodes in U outwards is minimized.
- 1 < n < number of vertices
Am I correct that neither k-MST or the Steiner tree approximation solutions will work? If so, what is this problem called? And what are the solutions? I am fine with using heuristics or approximations to solve this problem and don't need formal proofs.
I believe this is called the $k$-size cut problem. In general, it is NP hard though approximable since it is submodular. There was a discussion in the CS theory SE which may be useful to you, found here.
Of course, note that the problem there is the same problem except that $w \mapsto -w$, since we want to flip maximization/minimization, etc, etc.