6
$\begingroup$

This question first appeared at Hardness of node partitioning under shortest path constraint 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?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ (1) Are edge weights integers? If so, please state it in the question. (2) There seem to be several excessive “>” symbols in the question. $\endgroup$ – Tsuyoshi Ito Sep 28 '10 at 2:59
  • $\begingroup$ @Tsuyoshi the edge weights are integer. I edited the problem. $\endgroup$ – Kid Sep 28 '10 at 3:22
  • 1
    $\begingroup$ You added the tag [approximation-hardness]. Can you elaborate on how this question is related to hardness of approximation, preferably in the question? $\endgroup$ – Tsuyoshi Ito Sep 28 '10 at 15:44
  • $\begingroup$ @Tsuyoshi If the problem is strongly NP-complete, there's no pseudo-polynomial or FPTAS algorithm. $\endgroup$ – Kid Sep 28 '10 at 17:43
  • $\begingroup$ When you say FPTAS, which optimization problem are you talking about? $\endgroup$ – Tsuyoshi Ito Sep 29 '10 at 12:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.