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?

Improve this question
$\endgroup$
9
  • $\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, 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$
    – Tsuyoshi Ito
    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$
    – Tsuyoshi Ito
    Sep 29, 2010 at 12:39

0

Reset to default

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.