Hardness of node partitioning under shortest path constraint

Question

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 < |V|$?

Answer 1

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 S₁ and S₂ of S whose sums are equal to each other?

Let S={a₁, …, a_n} be a set of positive integers, where n=|S|. Construct a directed graph G with 2n vertices u₁, …, u_n, v₁, …, v_n by connecting u_i and v_i in both directions for each i. Give the weight a_i to the edge (u_i, v_i) and −a_i to the edge (v_i, u_i).

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(v_i)=l(u_i)+a_i. 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 S₁ and S₂ 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 H_l from G by removing the edges with negative weights and merging vertices with equal labels. Note that H_l has exactly n edges whose weights are a₁, …, a_n. Also, note that the number of vertices of H_l 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 H_l. Since H_l has at most n vertices and exactly n edges, H_l contains a cycle C ignoring the direction of edges. Let S₁ be the set of weights of edges appearing in C in one direction, and S₂ be the set of weights of edges appearing in C in the other direction. It is easy to see that the sum of S₁ is equal to the sum of S₂.

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

• l(u₁)=l(u_s+1)=0.
• l(u_i)=l(v_i−1) for 2≤i≤s and s+2≤i≤s+t.
• l(u_i)=0 for s+t+1≤i≤n.
• l(v_i)=l(u_i)+a_i for 1≤i≤n.

It is easy to verify that this assignment is feasible and uses at most n distinct labels. (The graph H_l 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