Does a reduction with $\infty$ work?

Question

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

Answer 1

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