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

• Could you explain how you solve the case where $k=|V|$? – Serge Gaspers Sep 21 '10 at 21:02
• indeed. Unless you can guarantee that w does not induce negative cycles, you might have a problem. – Suresh Venkat Sep 21 '10 at 21:50
• @Suresh: I do not think that negative cycles are problem because if w has is a negative cycle, we know that there are no solutions. – Tsuyoshi Ito Sep 22 '10 at 0:02
• I'm not sure if I got the problem formulation right: If the weights are nonnegative, then you can simply assign the label 0 to all nodes? Hence the problem is interesting only if you have negative weights; and with negative weights, the problem makes sense only if your graph is directed? – Jukka Suomela Sep 22 '10 at 8:47
• @Jukka @turkistany and @Tsuyoshi Yes. The graph is directed and admits negative weight. Otherwise the problem is trivial. Sorry, I didn't make it clear at first. I edited the question. Thanks. – Kid Sep 22 '10 at 14:20

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≤is and s+2≤is+t.
• l(ui)=0 for s+t+1≤in.
• l(vi)=l(ui)+ai for 1≤in.

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 nst 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

• What does "identifying vertices with equal labels" mean? Are they merged? – Kid Sep 25 '10 at 0:53
• @Kid: Yes, they are merged. I changed the wording in the answer. – Tsuyoshi Ito Sep 25 '10 at 1:01
• @Tsuyoshi, Is Equal Subset Sum strongly NP-complete? – Mohammad Al-Turkistany Sep 25 '10 at 5:45
• @turkistany: Good question. The answer is no (unless P=NP), because if the integers in the input are given in unary, you can compute the number $b_t$ of subsets summing up to t by simple dynamic programming. The answer to Equal Subset Sum is yes if and only if some t in the range $0\le t\le\sum_{i=1}^n a_i$ satisfies $b_t>1$. It seems that the problem in the question is also likely to have a pseudo-polynomial-time algorithm based on dynamic programming (assuming that the numbers in the input are integers), but I have not given much thought to it. – Tsuyoshi Ito Sep 25 '10 at 11:33
• @Tsuyoshi I'm also curious about whether this problem is strongly NP-complete. Though it is reduced from equal subset sum, which is weakly NP-complete, but the graph constructed is quite specialized (with $n/2$ pair of disjoint component and zero cycles between them). For general graph structure, it seems to be much more complicated. – Kid Sep 27 '10 at 18:32