I want to know the complexity of finding a set of M nodes, $\{U_1,\dots,U_M\}$, in a given graph $G$, to maximize $d(U_i,U_j)$ over all pairs $i\neq j$, where $d(\cdot,\cdot)$ is the length of the shortest path between two nodes.
I'm guessing this is NP-hard, but I'm looking for either a reference or a proof (or probably some combination of the two).
The specific graph I'm working with is the Grassmann graph $G_q(n,k)$ (all $k$-dimensional subspaces of the $n$-dimensional vector space over $\mathbb{F}_q$). The distance between any two nodes $U$ and $V$ is:
$$d(U,V) = k- \text{dim}(U\cap V)$$
However, the answer doesn't need to be specific to the Grassmann graph.
The problem you're trying to solve is called dispersion. This paper shows that it's NP-complete in general. It can be solved in polynomial time on trees (see this paper) but I'm not sure about your specific class of graphs.