Finding N nodes in a graph with maximum spread / distance from eachother

Question

Given a graph with N nodes (thousands), I need to find K nodes so that the average path length between each pair (K1,K2) of K is maximized. So basically, I want to place them as far away as possible from eachother.

Which algorithm would I use for this / how could I program this without having to try out several single combination of K?

Also as an extension: if I now have N nodes and I need to place 2 groups of nodes K and L in the graph such that the average path length between each pair (L,K) is maximized, how would I do this?

My current attempt is to just do a couple of random placements and then calculate the average path length between the pairs of both K and L, but this calculation is starting to take a lot of time so I'd rather not spend that much time on just evaluating randomly chosen combinations. I'd rather spend time once on getting the REAL most spread combination.

Are there any algorithms out there for this?

Answer 1

The bad news is that this problem is NP-hard, by a reduction from Independent Set. (Assume unit weights. Add a new vertex connected to all other vertices; then we're looking for a collection of K that have average distance 2.)

If you're determined to get an exact solution (and I'm not sure that you shouldn't be), then I'd try branch and bound, using node is/is not one of the K as the branching decision and a crude bound (given a subset of K, find the two nodes that maximize the appropriate combination of the distance between them and the distance to the subset, then set the bound to the appropriate weighted average incorporating the known inter-node distances).

If the exact algorithm above chokes on thousand-node graphs as Evgeny fears it will, then use a farthest-point clustering (link goes to the Wikipedia page on Facility Location, which describes FPC) to cut the graph to a manageable size, incurring a hopefully small approximation error.