patternMinor
Maximize distance between k nodes in a graph
Viewed 0 times
nodesgraphdistancebetweenmaximize
Problem
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?
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?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#41681, answer score: 8
Revisions (0)
No revisions yet.