# Does a reduction with $\infty$ work?

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

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

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$.
• Thank you. In the proof, the authors use $\infty$ to make a ratio equal to $0$. Is that correct? Mar 15, 2016 at 19:47
• You will have to replace $0$ with a very small number, $1/M$. Mar 15, 2016 at 19:49