Selecting k “special” nodes in a graph such that the min distance is maximized?

Question

Lets say we have a graph $G$ with $|V|$ nodes. We wish to select $k$ such nodes while optimizing the following attribute:

maximize: for each $i$ and $j$, where $i \neq j$, $min(distance(v_i, v_j))$

Hope that makes sense. We'd like to pick $k$ nodes such that the distance between the closest pair of distinct nodes is maximal.

Currently, my plan is to pick a node in random, find the node furthest away from it $v_0$ and the one furthest away from that node $v_1$. Now recursively look for nodes such that maximize the minimal distance from the selected node set. Meaning, nodes that have the greatest distance possible from the any selected node and specifically the member closest to them of the previously selected set of nodes.

The issue with this is that it's greedy and therefore possibly very inaccurate.

Answer 1

Assuming $k$ is part of the input, the problem is NP-hard (by reduction from Independent Set; there's an independent set of size $k$ if and only if there's a way to solve your problem and achieve a minimum distance of 2 or greater).

Your current plan is known as the furthest-point heuristic. It's a heuristic, because it won't necessarily give the optimal solution, though often it gives a solution that's reasonably good. The furthest-point heuristic has been used, among other things, as a technique to select the initial values for $k$-means clustering.

If you want to find an exact solution, you could express this as an instance of of ILP or SAT. Suppose we want to test whether min-distance $t$ is achievable. For each variable $v$, you have a boolean variable $x_v$ that's 1 if $v$ is selected or 0 otherwise. Now for each pair of nodes $u,v$ such that $d(u,v)<t$, you add a constraint saying that you cannot choose both $u$ and $v$ (e.g., the constraint $x_u+x_v \le 1$ or $(\neg x_u \lor \neg x_v)$). Finally, you add a constraint that exactly $k$ nodes much be selected, and then you test whether these constraints are satisfiable. If they are, min-distance $t$ is achievable. Now repeat using binary search to find the largest $t$ such that the instance is satisfiable.