Relaxed graph coloring, with penalties for assigning adjacent vertices the same color Consider a set of $N$ nodes. There is a $N\times N$ non-negative valued matrix $D$ where the $(i,j)$th element $d_{ij}$ gives the "positive metric" between node $i$ and $j$, where $i,j\in [N]$. Thus the diagonal entries of $D$ are all zero and $d_{ij}=d_{ji}$ so $D$ is symmetric. 

Then there is a set of  $k$ colors. I want to assign these colors to the $N$ nodes such that the minimum  metric of a common color between any pair of nodes is maximized. So if $c(i)$ is the color assigned to $i\in [N]$ by the assignment $a\in A$, where $A$ is the set of all possible color assignments, we are looking for $$\max_{a\in A} \min_{i,j} \{d_{ij}:c(i)=c(j)\}.$$

Is this problem NP-hard?  If it is, what sort of reduction can be used to show that this problem is NP-hard?
Yes. Reduce from graph coloring.

$D$ is given by $d_{i,j} = \begin{cases} 0 &amp; \text{ if } i=j \\ 1 &amp; \text{ if } i \text{ is adjacent to } j \\ 2 &amp; \text{ else}\end{cases}$.