In a very famous paper (in the networking community), Wang & Crowcroft present some $\mathsf{NP}$-completeness results of path computation under several additive/multiplicative constraints. The first problem is the following :

Given a directed graph $G=(V,A)$ and two weight metrics $w_1$ and $w_2$ over the edges, define, for a path $P$, $w_i(P)=\sum_{a\in P}w_i(a)$ ($i=1,2$). Given two nodes $s$ and $t$, the problem is to find a path $P$ from $s$ to $t$ s.t. $w_i(P)\leq W_i$, where the $W_i$ are given positive numbers (example: Delay constraint and cost in a network).

The authors prove that this problem is $\mathsf{NP}$-complete by providing a polynomial reduction from PARTITION.

Then they present the same problem except that the metrics are multiplicative, i.e., $w'_i(P)=\prod_{a\in P}w'_i(a)$. In order to prove the multiplicative version is $\mathsf{NP}$-complete, they provide a "polynomial" reduction from the additive version just by putting $w'_i(a)=e^{w_i(a)}$ and $W'_i=e^{W_i}$.

I am very puzzled by this reduction. Since $W'_i$ and $w'_i(a)$ are part of the input (in binary, I guess), then the $|w'_i(a)|$ and $|W'_i|$ are not polynomial in $|w_i(a)|$ and $|W_i|$. Thus the reduction is not polynomial.

Am I missing something trivial or there is a flaw in the proof?

Paper reference : Zheng Wang, Jon Crowcroft. Quality-of-Service Routing for Supporting Multimedia Applications. IEEE Journal on Selected Areas in Communications 14(7): 1228-1234 (1996).

  • $\begingroup$ I would be very surprised if there were a flaw, since D. S. Johnson itself checked the proof. $\endgroup$
    – Lamine
    Nov 23, 2016 at 18:13
  • $\begingroup$ Haven't read the paper carefully yet, so I'm not sure if $w_i$ constructed in their reduction from PARTITION can be taken exponential. However the multiplicative counterpart of PARTITION is also $\textsf{NP-hard}$; could this help? $\endgroup$
    – Wei Zhan
    Nov 23, 2016 at 19:13
  • $\begingroup$ Welcome to CS.SE! Can you edit the question to give a full reference to the paper (title, authors, and where published), so this question shows up if anyone else with the same question searches for the paper, and so we can find the paper again if the link stops working? Thank you! $\endgroup$
    – D.W.
    Nov 23, 2016 at 19:20
  • 1
    $\begingroup$ @WillardZhan The multiplicative version of the problem is indeed $\mathsf{NP}$-complete. It can be shown by a reduction from MULTIPLICATIVE PARTITION (as you suggest) or Knapsack problem. My doubt is about the validity of the proof, even if the result is clearly true. $\endgroup$
    – Lamine
    Nov 24, 2016 at 12:41
  • 2
    $\begingroup$ Note: after receiving no answer here in nearly two weeks, this question has been reposted to CS Theory. $\endgroup$ Dec 5, 2016 at 16:38


Browse other questions tagged or ask your own question.