# Further question on hardness of node partitioning under shortest path constraint

This question first appeared at Hardness of node partitioning under shortest path constraint and I restate it here

Given a direct graph $G=(V,E)$. $\forall (i,j) \in E$, there is a weight $w(i,j) \in \mathbb{Z}$ (integer and negative weight is possible). A label $l(i)$ is associated with each node $i \in V$. How to assign $k$ (or less) distinctive values to $l(i)$ such that
$$l(j) \leq l(i) + w(i,j),\quad \forall (i,j) \in E ?$$ Notice that when $k=|V|$, this problem is easily solvable by Shortest path algorithm (Bellman-Ford). But what's the hardness is this problem for $k < |V|$?

@Tsuyoshi has proved this problem to be NP-complete in the original post. Although the reduction is from a weakly NP-complete problem "equal subset sum", the problem listed above seems to be more complicated. So my further question is whether this problem is strongly or weakly NP-complete?

• (1) Are edge weights integers? If so, please state it in the question. (2) There seem to be several excessive “>” symbols in the question. – Tsuyoshi Ito Sep 28 '10 at 2:59
• @Tsuyoshi the edge weights are integer. I edited the problem. – Kid Sep 28 '10 at 3:22
• You added the tag [approximation-hardness]. Can you elaborate on how this question is related to hardness of approximation, preferably in the question? – Tsuyoshi Ito Sep 28 '10 at 15:44
• @Tsuyoshi If the problem is strongly NP-complete, there's no pseudo-polynomial or FPTAS algorithm. – Kid Sep 28 '10 at 17:43
• When you say FPTAS, which optimization problem are you talking about? – Tsuyoshi Ito Sep 29 '10 at 12:39