Maximize distance between k nodes in a graph

I have an undirected unweighted graph $G$ and I want to select $k$ nodes from $G$ such that they are pairwise as far as possible from each other, in terms of geodesic distance. In other words they have to be spread around the graph as possible.

Let $d(u,v)$ be the length of a shortest path between $u$ and $v$ in $G$. Now, for a set of vertices $X \subseteq V(G)$, define $$d(X) = \sum_{\{u,v\} \subseteq X}d(u,v).$$

Let the problem SCATTERED SET be the problem which on input $G,k$ asks to find a set of $k$ vertices $X$ maximizing $d(X)$.

Is there an efficient algorithm solving SCATTERED SET?

• @D.W. The objective would be to maximize the distance between all the chosen nodes. So in your example 5,5,5 would be better since it would be 15. Another way to look at it is that I need to maximize the number of intermediate nodes in the graph one would need to traverse in order to eventually visit all the chosen nodes. Not so sure about clustering, do you have any particular approach in mind?
– jbx
Apr 22 '15 at 5:51
• This is somewhat similar to the geodetic number problem. A set of vertices $X$ of a graph $G$ is geodetic if every vertex of $G$ lies on a shortest path between two (not necessarily) distinct vertices in $X$. Given a graph $G$ and an integer $k$, the problem is to decide if $G$ has a geodetic set of cardinality at most $k$. The problem is NP-complete even for chordal bipartite graphs.
– Juho
Apr 22 '15 at 6:34
• The objective can be rewritten as to maximizing the average distance. Apr 22 '15 at 7:23
• somewhat similar to finding hubs/ centers in a graph
– vzn
Jul 1 '15 at 21:43

I don't know if there is a polynomial-time algorithm (it feels like it might be NP-hard), but here are some plausible algorithmic approaches you might could consider, if you need to solve it in practice:

Heuristics

One well-explored algorithm is Furthest Point First (FPF). At each iteration, it chooses a point that is furthest from the set of points selected so far. Iterate $k$ times. As this is a greedy strategy, there is no reason to expect this to give an optimal answer or even close to optimal, and it was designed to optimize a slightly different objective function... but in some contexts it gives a reasonable approximation, so it could be worth a try.

FPF comes out of the literature on graph-based clustering and was introduced in the following research paper:

Teofilo F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, vol 38, pp.293-306, 1985.

You could try exploring the literature on graph-based clustering to see if anyone has studied your specific problem.

Exact algorithms

If you have this problem in practice and need an exact optimum solution, you could try to solve this using an ILP solver.

Here's how. Introduce 0-or-1 variables $x_i$, where $x_i$ indicates whether the $i$th vertex was selected, and 0-or-1 variables $y_{i,j}$, with the intended meaning that $y_{i,j}=1$ only if $x_i=1$ and $x_j=1$. Now maximize the objective function $\sum_{i,j} d(i,j) y_{i,j}$, subject to the constraints $\sum x_i \le k$ and $x_i \ge y_{i,j}$ and $x_j \ge y_{i,j}$. Now solve this ILP with an off-the-shelf ILP solver. As ILP is NP-hard, there's no guarantee this will be efficient, but it might work on some problem instances.

Another approach is to use weighted MAX-SAT. In particular, introduce boolean variables $x_i$, where $x_i$ is true if the $i$th vertex was selected, and variables $y_{i,j}$. The formula is $\phi \land \land_{i,j} y_{i,j}$, where $\phi$ must be true (its clauses have weight $W$ for some very large $W$) and each clause $y_{i,j}$ is given weight $d(i,j)$. Define the formula $\phi$ to be true if at most $k$ of the $x_i$'s are true (see here for details on how to do that) and if $y_{i,j}=x_i \land x_j$ for all $i,j$. Now the solution to this weighted MAX-SAT problem is the solution to the original problem, so you could try throwing a weighted MAX-SAT solver at the problem. The same caveats apply.

No, the problem is NP-complete.

Let $(G,k)$ be an instance of INDEPENDENT SET. Construct $G'$ by adding a universal vertex $u$ to $G$. The crucial observation is that the distance between two vertices in $G$ is 1 in $G'$ if and only if they are adjacent in $G$, and 2 otherwise.

Now, the optimal solution of SCATTERED SET on input $(G',k)$ is $2\binom{k}{2}$ if and only if $G$ has an independent set of size $k$.