# Does a problem remain tractable If a single discrete variable becomes continuous?

Let $$\mathcal{F}$$ be a family of pairs of the form $$(A,b)$$, where $$A$$ is an integer matrix and $$b$$ is an integer vector with the same number of rows. For every integer $$k$$, define $$L(\mathcal{F}, k)$$ to be the following family of decision problems.

INPUT: a pair $$(A,b)\in \mathcal{F}$$.

OUTPUT: "True" if there exists a real vector $$x \geq 0$$ satisfying $$A x \leq b$$, where for every $$i > k$$, $$x_i$$ must be an integer (for $$i\leq k$$, $$x_i$$ can be any real number).

If $$k=0$$, then these are simply integer programming problems, and $$L(\mathcal{F}, k)$$ is NP-hard in general. But it is in P for some subclasses of matrices and vectors, for example, when for all $$(A,b)\in \mathcal{F}$$, the matrix $$A$$ is of totally unimodular.

I am interested in the effect of $$k$$ on the complexity of $$L(\mathcal{F}, k)$$. In particular, if $$L(\mathcal{F}, k)$$ is in P for some $$k$$, does it imply that $$L(\mathcal{F}, k+1)$$ is in P too?

Stated informally: if we take a single discrete variable and allow it to be continuous, does the problem remain tractable?

EDIT: Here is an example showing that the opposite is possible: if we start from an NP-hard problem, and convert a single discrete variable to continuous, the problem may become tractable. Consider the following family of linear programs: $$a_1 x_1 + \cdots + a_n x_n = (a_1+ \cdots +a_n)/2 \\ 0 \leq x_i \leq 1 ~~~ \forall i\in\{1,\ldots,n\} \\ x_i \in \mathbb{Z} ~~~ \forall i\in\{1,\ldots,n\}$$ where the input is the integer vector $$a_1,\ldots,a_n$$ and the output is "true" if there is a vector $$x_1,\ldots,x_n$$ satisfying the constraint. This LP represents the NP-hard partition problem.

Suppose w.l.o.g. that the input arrives in descending order ($$a_1\geq \cdots \geq a_n$$). Then, if we allow a single variable $$x_1$$ to be continuous (we remove the constraint $$x_1\in \mathbb{Z}$$), then the problem becomes tractable: if the largest item can be split, then the answer is always "yes". So, $$L(\mathcal{F}, 1)$$ is in $$P$$ while $$L(\mathcal{F}, 0)$$ is NP-hard.

Is there an $$\mathcal{F}$$ for which the opposite holds --- $$L(\mathcal{F}, 1)$$ is in $$P$$ while $$L(\mathcal{F}, 0)$$ is NP-hard?

EDIT 2: Note that, without the restriction to linear problems, even making all variables continuous might make a problem harder. See this answer.

• In some cases, yes! For example, when number of integer variables are bounded by some constant. Apr 21 at 14:41
• I do not understand. Can you elaborate? Apr 22 at 20:13

Therefore, if any $$L(\mathcal{A}, \mathcal{B}, k)$$ is in $$\mathsf{P}$$ for some $$k$$, and suppose that $$n-k = O(1)$$ where $$n$$ is the number of elements in $$x$$. Then, it trivially implies that $$L(\mathcal{A}, \mathcal{B}, k+1)$$ is in $$\mathsf{P}$$ too, since $$L(\mathcal{A}, \mathcal{B}, k+1)$$ can be solved in polynomial time (there are at most $$n-k-1 = O(1)$$ integer variables in $$L(\mathcal{A}, \mathcal{B}, k+1)$$).
• This assumes that $n-k= O(1)$. What if this is not the case? Apr 25 at 13:25