1
$\begingroup$

Lately, I saw an NP-complete proof that involves creating an instance of a problem using $\infty$. Is this a polynomial-time reduction?

More precisely, let a problem $\Pi$ has an instance $I=(n, A, v)$ where $A$ is a matrix of size $n\times n$, $A=[a_{ij}]$, and $v$ is positive.

The proof that $\Pi$ is NP-complete works by reducing the independent set problem (an instance is a graph $G=(V,E)$ and an integer $k$) to $\Pi$ as follows: $n=|V|,v=k$ and

$$a_{ij} = \begin{cases} \infty \text{ if } \{i,j\}\in E\\ 0, \text{ otherwise } \end{cases}.$$ Also, $G$ has an independent set of size $k\iff\Pi$ has a value $v= k$.

I do not see how one can set $a_{ij}$ to $\infty$.

$\endgroup$
3
  • $\begingroup$ What problem is $\Pi$? ​ ​ $\endgroup$
    – user12859
    Mar 15, 2016 at 17:34
  • $\begingroup$ Does it matter? $\endgroup$
    – drzbir
    Mar 15, 2016 at 19:46
  • $\begingroup$ Probably. ​ See Yuval's answer. ​ ​ ​ ​ $\endgroup$
    – user12859
    Mar 15, 2016 at 19:50

1 Answer 1

4
$\begingroup$

In most cases in which such a reduction is presented, the reduction also works with $\infty$ replaced by a large enough number $M$ which is at most exponential in some power of $n$. If you replace $\infty$ by $M$ then you get a bona fide instance of $\Pi$, and this instance has polynomial size (and so the reduction runs in polynomial time) since $|M| = O(n^C)$ for some $C$, where $|M|$ is the length of the binary encoding of $M$.

You are right that using $\infty$ instead of $M$ is a bit sloppy, but it often results in a cleaner description, it being understood that the "real" reduction uses some large enough finite $M$.

$\endgroup$
2
  • $\begingroup$ Thank you. In the proof, the authors use $\infty$ to make a ratio equal to $0$. Is that correct? $\endgroup$
    – drzbir
    Mar 15, 2016 at 19:47
  • 1
    $\begingroup$ You will have to replace $0$ with a very small number, $1/M$. $\endgroup$ Mar 15, 2016 at 19:49

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.