15
$\begingroup$

I asked this question 10 days ago on cs.stackexchange here but I didn'y have any answer.

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 is there a flaw in the proof? My doubt is about the validity of the proof, even if the result is clearly true.

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).

$\endgroup$
  • 1
    $\begingroup$ I've checked the paper, this is surely a flaw in their proof. $\endgroup$ – domotorp Dec 5 '16 at 13:16
  • $\begingroup$ The paper is cited more than 2000 times. This is scary... $\endgroup$ – Lamine Dec 5 '16 at 15:13
  • $\begingroup$ Well, probably most citations don't use this particular result, and also, after all, it is still true. I was told examples when they had to withdraw several papers building on a false result. Also, this exponentiation trick is so standard that probably most people don't even think it through and realize what you did, that the length of the input changes. $\endgroup$ – domotorp Dec 5 '16 at 20:51
9
$\begingroup$

The proof as presented in the paper is not conclusive.

However, the stated result itself is correct. It can easily be derived by slightly changing the reduction and by using SUBSET PRODUCT instead of SUBSET SUM.

A useful link for the SUBSET PRODUCT problem:
https://cs.stackexchange.com/questions/7907/is-the-subset-product-problem-np-complete

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.