<p>This question first appeared at <a href="https://cstheory.stackexchange.com/q/1555/1351">Hardness of node partitioning under shortest path constraint</a> and I restate it here</p>

<blockquote>
  <p>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<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>
</blockquote>

<p>@Tsuyoshi has proved this problem to be <strong>NP-complete</strong> 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 <strong>whether this problem is strongly or weakly NP-complete</strong>?</p>

CC BY-SA 2.5
2010-09-28T02:59:31.433Z
(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
CC BY-SA 2.5
2010-09-28T03:22:55.097Z
@Tsuyoshi the edge weights are integer. I edited the problem.
Kid
CC BY-SA 2.5
2010-09-28T15:44:18.953Z
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
CC BY-SA 2.5
2010-09-28T17:43:08.273Z
@Tsuyoshi If the problem is strongly NP-complete, there's no pseudo-polynomial or FPTAS algorithm.
Kid
CC BY-SA 2.5
2010-09-29T12:39:53.323Z
When you say FPTAS, which optimization problem are you talking about?
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-29T14:12:25.387Z
Currently I have no idea about this..
Kid
CC BY-SA 2.5
2010-09-29T22:11:48.213Z
Then I do not think that you should tag the question as [approximation-hardness].  If/when you are sure that the question is related to hardness of approximation, it will be helpful to state the relation in the question and add the tag.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-29T22:35:26.570Z
Ok. Let me remove it.
Kid
CC BY-SA 2.5
2010-09-29T23:38:50.903Z
Presumably the relevant parameter is k, but since this is integral, you can't get an FPTAS anyway
Suresh Venkat
<graph-theory><np-hardness>
Further question on hardness of node partitioning under shortest path constraint
Kid
# Further question on hardness of node partitioning under shortest path constraint

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

This question first appeared at [Hardness of node partitioning under shortest path constraint](https://cstheory.stackexchange.com/q/1555/1351) 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**?

**Tags:** graph-theory, np-hardness
> **Comments:**
> **username_1**: (1) Are edge weights integers?  If so, please state it in the question.  (2) There seem to be several excessive “>” symbols in the question.  
> **username_0**: @Tsuyoshi the edge weights are integer. I edited the problem.  
> **username_1**: You added the tag [approximation-hardness].  Can you elaborate on how this question is related to hardness of approximation, preferably in the question?  
> **username_0**: @Tsuyoshi If the problem is strongly NP-complete, there's no pseudo-polynomial or FPTAS algorithm.  
> **username_1**: When you say FPTAS, which optimization problem are you talking about?  
> **username_0**: Currently I have no idea about this..  
> **username_1**: Then I do not think that you should tag the question as [approximation-hardness].  If/when you are sure that the question is related to hardness of approximation, it will be helpful to state the relation in the question and add the tag.  
> **username_0**: Ok. Let me remove it.  
> **username_2**: Presumably the relevant parameter is k, but since this is integral, you can't get an FPTAS anyway  

---

## 0 answers

