Relaxed graph coloring, with penalties for assigning adjacent vertices the same color
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}$.