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?

  • $\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$ Sep 28, 2010 at 2:59
  • $\begingroup$ @Tsuyoshi the edge weights are integer. I edited the problem. $\endgroup$
    – Kid
    Sep 28, 2010 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$ Sep 28, 2010 at 15:44
  • $\begingroup$ @Tsuyoshi If the problem is strongly NP-complete, there's no pseudo-polynomial or FPTAS algorithm. $\endgroup$
    – Kid
    Sep 28, 2010 at 17:43
  • $\begingroup$ When you say FPTAS, which optimization problem are you talking about? $\endgroup$ Sep 29, 2010 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.