<p>Let’s call an assignment of vertex labels <em>feasible</em> if it satisfies all the inequality constraints, ignoring the condition on the number of distinct labels.</p>

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

<p>Equal Subset Sum<br>
<em>Instance</em>: A finite set <i>S</i> of positive integers.<br>
<em>Question</em>: Do there exist two disjoint nonempty subsets <i>S</i><sub>1</sub> and <i>S</i><sub>2</sub> of <i>S</i> whose sums are equal to each other?</p>

<p>Let <i>S</i>={<i>a</i><sub>1</sub>, …, <i>a</i><sub><i>n</i></sub>} be a set of positive integers, where <i>n</i>=|S|.  Construct a directed graph <i>G</i> with 2<i>n</i> vertices <i>u</i><sub>1</sub>, …, <i>u</i><sub><i>n</i></sub>, <i>v</i><sub>1</sub>, …, <i>v</i><sub><i>n</i></sub> by connecting <i>u</i><sub><i>i</i></sub> and <i>v</i><sub><i>i</i></sub> in both directions for each <i>i</i>.  Give the weight <i>a</i><sub><i>i</i></sub> to the edge (<i>u</i><sub><i>i</i></sub>, <i>v</i><sub><i>i</i></sub>) and −<i>a</i><sub><i>i</i></sub> to the edge (<i>v</i><sub><i>i</i></sub>, <i>u</i><sub><i>i</i></sub>).</p>

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

<p><strong>Claim</strong>.  <i>G</i> has a feasible assignment which uses at most <i>n</i> distinct labels if and only if there exist two disjoint nonempty subsets <i>S</i><sub>1</sub> and <i>S</i><sub>2</sub> of <i>S</i> whose sums are equal to each other.</p>

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

<p>For the “only if” direction, given a feasible assignment <i>l</i> which uses at most <i>n</i> distinct labels, consider the directed graph <i>H</i><sub><i>l</i></sub>.  Since <i>H</i><sub><i>l</i></sub> has at most <i>n</i> vertices and exactly <i>n</i> edges, <i>H</i><sub><i>l</i></sub> contains a cycle <i>C</i> ignoring the direction of edges.  Let <i>S</i><sub>1</sub> be the set of weights of edges appearing in <i>C</i> in one direction, and <i>S</i><sub>2</sub> be the set of weights of edges appearing in <i>C</i> in the other direction.  It is easy to see that the sum of <i>S</i><sub>1</sub> is equal to the sum of <i>S</i><sub>2</sub>.</p>

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

<ul>
<li><i>l</i>(<i>u</i><sub>1</sub>)=<i>l</i>(<i>u</i><sub><i>s</i>+1</sub>)=0.</li>
<li><i>l</i>(<i>u</i><sub><i>i</i></sub>)=<i>l</i>(<i>v</i><sub><i>i</i>−1</sub>) for 2≤<i>i</i>≤<i>s</i> and <i>s</i>+2≤<i>i</i>≤<i>s</i>+<i>t</i>.</li>
<li><i>l</i>(<i>u</i><sub><i>i</i></sub>)=0 for <i>s</i>+<i>t</i>+1≤<i>i</i>≤<i>n</i>.</li>
<li><i>l</i>(<i>v</i><sub><i>i</i></sub>)=<i>l</i>(<i>u</i><sub><i>i</i></sub>)+<i>a</i><sub><i>i</i></sub> for 1≤<i>i</i>≤<i>n</i>.</li>
</ul>

<p>It is easy to verify that this assignment is feasible and uses at most <i>n</i> distinct labels.  (The graph <i>H</i><sub><i>l</i></sub> 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 <i>n</i>−<i>s</i>−<i>t</i> edges originating at the vertex labeled 0.)  <strong>QED</strong>.</p>

<p>References</p>

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

CC BY-SA 2.5
2010-09-25T00:53:53.590Z
What does "identifying vertices with equal labels" mean? Are they merged?
Kid
CC BY-SA 2.5
2010-09-25T01:01:19.903Z
@Kid: Yes, they are merged.  I changed the wording in the answer.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-25T05:45:14.710Z
@Tsuyoshi, Is Equal Subset Sum strongly NP-complete?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-25T11:33:29.670Z
@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
CC BY-SA 2.5
2010-09-27T18:32:41.217Z
@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
CC BY-SA 2.5
2010-09-27T20:44:11.897Z
@Kid: Sounds like a candidate for a separate question.  The pseudo-polynomial-time algorithm I had in mind seems to work only in the case where k is a constant, and I am no longer sure whether the current problem has a pseudo-polynomial-time algorithm or not.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-27T21:33:38.073Z
@Tsuyoshi What do you mean by "k is a constant"? I modified the original question to further discuss the hardness of this problem. You answer above is still valid.
Kid
CC BY-SA 2.5
2010-09-27T21:48:37.907Z
@Kid: I think that you should have posted a separate question, linking to this question (partly because I think that the original question was already answered, partly because my answer is too long).  As for k being constant, the algorithm I was thinking about runs in time $O(((|V|+|E|)S)^k)$ (or something like that), where S is the sum of the absolute values of weights of all edges, assuming all weights are integers.  It is pseudo-polynomial-time only if k is a constant, not something like k=|V|/2.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-27T21:59:09.123Z
@Kid: As for whether to post a separate question or edit a question, you may want to ask the opinions of other people.  In that case, please post a question on [meta](http://meta.cstheory.stackexchange.com/), linking to this question.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-28T00:44:11.993Z
@Tsuyoshi Thanks. I started a new post about this question.
Kid
CC BY-SA 2.5
2010-09-24T22:26:31.713Z
2010-09-25T01:00:39.123Z
2010-09-25T01:00:39.123Z
Tsuyoshi Ito
<p>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<br>
$$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|$? </p>

CC BY-SA 2.5
2010-09-21T21:02:46.230Z
Could you explain how you solve the case where $k=|V|$?
Serge Gaspers
CC BY-SA 2.5
2010-09-21T21:50:17.133Z
indeed. Unless you can guarantee that w does not induce negative cycles, you might have a problem.
Suresh Venkat
CC BY-SA 2.5
2010-09-22T00:02:06.130Z
@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
CC BY-SA 2.5
2010-09-22T01:37:45.463Z
@serge if $k=|V|$, we can run Bellman-Ford, the algorithm gives $l(i)$ for all $i \in V$ upon termination. Or, like what @Ito said, detects a negative cycle, indicating no solution. Oh, There might be a problem if in the result, there's $l(i)=l(j)$ for some $i \neq j$. In this case we get the solution for some $k < |V|$. Yes, that's a problem...
Kid
CC BY-SA 2.5
2010-09-22T01:44:04.577Z
@Serge I slightly modify the definition of the problem, asking for $k$ or less distinctive groups.
Kid
CC BY-SA 2.5
2010-09-22T01:58:16.353Z
If k=|V|−1, you can try all the $\binom{|V|}{2}$ possibilities of making two labels equal, and therefore the problem can be solved in polynomial time.  The same holds for the case where k=|V|−O(1).
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-22T08:47:17.527Z
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
CC BY-SA 2.5
2010-09-22T11:54:45.207Z
@Jukka: I assumed implicitly that the input graph was directed, but I agree that it is better to make it explicit if that is the case.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-22T14:20:48.600Z
@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
<graph-theory><np-hardness>
Hardness of node partitioning under shortest path constraint
Kid
# Hardness of node partitioning under shortest path constraint

(Asked by: username_0 on 2010-09-21)

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

**Tags:** graph-theory, np-hardness

> **Comments:**
> **username_1**: Could you explain how you solve the case where $k=|V|$?  
> **username_2**: indeed. Unless you can guarantee that w does not induce negative cycles, you might have a problem.  
> **username_3**: @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.  
> **username_0**: @serge if $k=|V|$, we can run Bellman-Ford, the algorithm gives $l(i)$ for all $i \in V$ upon termination. Or, like what @Ito said, detects a negative cycle, indicating no solution. Oh, There might be a problem if in the result, there's $l(i)=l(j)$ for some $i \neq j$. In this case we get the solution for some $k < |V|$. Yes, that's a problem...  
> **username_0**: @Serge I slightly modify the definition of the problem, asking for $k$ or less distinctive groups.  
> **username_3**: If k=|V|−1, you can try all the $\binom{|V|}{2}$ possibilities of making two labels equal, and therefore the problem can be solved in polynomial time.  The same holds for the case where k=|V|−O(1).  
> **username_4**: 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*?  
> **username_3**: @Jukka: I assumed implicitly that the input graph was directed, but I agree that it is better to make it explicit if that is the case.  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_3 on 2010-09-24. Score: 4 | Accepted answer

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*1 and *S*2 of *S* whose sums are equal to each other?

Let *S*={*a*1, …, *a**n*} be a set of positive integers, where *n*=|S|. Construct a directed graph *G* with 2*n* vertices *u*1, …, *u**n*, *v*1, …, *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*1 and *S*2 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*1, …, *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*1 be the set of weights of edges appearing in *C* in one direction, and *S*2 be the set of weights of edges appearing in *C* in the other direction. It is easy to see that the sum of *S*1 is equal to the sum of *S*2.

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

* *l*(*u*1)=*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>

> **Comments:**
> **username_0**: What does "identifying vertices with equal labels" mean? Are they merged?  
> **username_3**: @username_0: Yes, they are merged.  I changed the wording in the answer.  
> **username_5**: @Tsuyoshi, Is Equal Subset Sum strongly NP-complete?  
> **username_3**: @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.  
> **username_0**: @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.  
> **username_3**: @username_0: Sounds like a candidate for a separate question.  The pseudo-polynomial-time algorithm I had in mind seems to work only in the case where k is a constant, and I am no longer sure whether the current problem has a pseudo-polynomial-time algorithm or not.  
> **username_0**: @Tsuyoshi What do you mean by "k is a constant"? I modified the original question to further discuss the hardness of this problem. You answer above is still valid.  
> **username_3**: @username_0: I think that you should have posted a separate question, linking to this question (partly because I think that the original question was already answered, partly because my answer is too long).  As for k being constant, the algorithm I was thinking about runs in time $O(((|V|+|E|)S)^k)$ (or something like that), where S is the sum of the absolute values of weights of all edges, assuming all weights are integers.  It is pseudo-polynomial-time only if k is a constant, not something like k=|V|/2.  
> **username_3**: @username_0: As for whether to post a separate question or edit a question, you may want to ask the opinions of other people.  In that case, please post a question on [meta](http://meta.cstheory.stackexchange.com/), linking to this question.  
> **username_0**: @Tsuyoshi Thanks. I started a new post about this question.  

---

