Hardness of node partitioning under shortest path constraint Given a direct graph $G=(V,E)$. $\forall (i,j) \in E$, there is a weight $w(i,j) \in R$ (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 &lt; |V|$?
Let’s call an assignment of vertex labels feasible if it satisfies all the inequality constraints, ignoring the condition on the number of distinct labels.

Here is what I think is a proof that it is NP-complete to decide whether a given directed graph G=(V, E) with integer (possibly negative) edge weights has a feasible assignment of labels which uses at most k distinct labels, for k=|V|/2.  We construct a reduction from the following NP-complete problem [WY92].

Equal Subset Sum
Instance: A finite set S of positive integers.
Question: Do there exist two disjoint nonempty subsets S1 and S2 of S whose sums are equal to each other?

Let S={a1, …, an} be a set of positive integers, where n=|S|.  Construct a directed graph G with 2n vertices u1, …, un, v1, …, vn by connecting ui and vi in both directions for each i.  Give the weight ai to the edge (ui, vi) and −ai to the edge (vi, ui).

Consider the instance (G, n) of the current problem.  Note that an assignment l of labels is feasible if and only if for each i, it holds l(vi)=l(ui)+ai.  From this, we can prove the following, establishing that the above transformation is a reduction from Equal Subset Sum to the current problem.

Claim.  G has a feasible assignment which uses at most n distinct labels if and only if there exist two disjoint nonempty subsets S1 and S2 of S whose sums are equal to each other.

Proof.  First observe that if we are given a feasible assignment l (which might use any number of distinct labels), we can construct a directed graph Hl from G by removing the edges with negative weights and merging vertices with equal labels.  Note that Hl has exactly n edges whose weights are a1, …, an.  Also, note that the number of vertices of Hl is equal to the number of distinct labels used in l.

For the “only if” direction, given a feasible assignment l which uses at most n distinct labels, consider the directed graph Hl.  Since Hl has at most n vertices and exactly n edges, Hl contains a cycle C ignoring the direction of edges.  Let S1 be the set of weights of edges appearing in C in one direction, and S2 be the set of weights of edges appearing in C in the other direction.  It is easy to see that the sum of S1 is equal to the sum of S2.

For the “if” direction, fix S1 and S2 be the subsets of S satisfying the condition.  Without loss of generality, assume that S1={a1, a2, …, as} and S2={as+1, as+2, …, as+t}, where s=|S1| and t=|S2|.  Then we assign the following labels to the vertices of G:


l(u1)=l(us+1)=0.
l(ui)=l(vi−1) for 2≤i≤s and s+2≤i≤s+t.
l(ui)=0 for s+t+1≤i≤n.
l(vi)=l(ui)+ai for 1≤i≤n.


It is easy to verify that this assignment is feasible and uses at most n distinct labels.  (The graph Hl in this case consists of two edge-disjoint paths from the vertex labeled 0 to the vertex labeled $\sum_{i=1}^s a_i = \sum_{i=s+1}^{s+t} a_i$ and n−s−t edges originating at the vertex labeled 0.)  QED.

References

[WY92] Gerhard J. Woeginger and Zhongliang Yu.  On the equal-subset-sum problem.  Information Processing Letters, 42(6):299–302, July 1992.  http://dx.doi.org/10.1016/0020-0190(92)90226-L