# Solving an LP with at most m-1 nonzeros

Consider the linear program:

$$A x = b, ~~~~~~ x\geq 0$$ where $$A$$ is an $$m$$-by-$$n$$ matrix, $$x$$ is an $$n$$-by-1 vector, $$b$$ is an $$m$$-by-1 vector, and $$m.

It is known that, if this program has a solution, then it has a basic feasible solution, in which at most $$m$$ variables are non-zero.

QUESTION: is there an efficient algorithm to decide whether the LP has a solution in which at most $$m-1$$ variables are non-zero, and find it if it exists?

The question is a special case of Min-RVLS - finding a solution with a smallest number of non-zero variables. Min-RVLS is known to be NP-hard and hard to approximate within a multiplicative factor. Finding an additive approximation is hard too.

But, here our goal is much more modest - all we want is to find a solution with one less than the maximum ($$m$$). Is this special case easier?

This question was previously posted in cs.SE and got no answers. I deleted it from there to avoid cross-posting.

I think the "few nonzeros" problem is NP-hard, by reduction from the partition problem. Suppose we are given $$m$$ numbers $$a_1,\ldots,a_m$$ whose total sum is $$2 s$$, and have to decide whether they can be partitioned into two subsets such that the sum in each subset is $$s$$. We can solve this problem using a linear program with $$2 m$$ variables. For each $$i\in[2]$$ and $$j\in [m]$$, the variable $$x_{ij}$$ determines what fraction of the number $$a_j$$ is in subset $$i$$. There are $$m+1$$ constraints (besides non-negativity):

• For each $$j\in[m]$$: $$x_{1j}+x_{2j} = 1$$
• The equal-sum constraint: $$\sum_{j=1}^m x_{1j} a_j = \sum_{j=1}^m x_{2j} a_j$$

There always exists a solution with at most $$m+1$$ nonzeros. In this solution, at most one number is "cut" between the sets. Indeed, it is easy to solve the partition problem if we are allowed to cut one number: just order the numbers on a line and cut the line into two parts with equal sum.

Now, if we could solve the "few nonzeros" problem, then we could decide whether the above LP has a solution with at most $$m$$ nonzeros, which would imply a solution to the partition problem (in which no number is cut). But this problem is known to be NP-complete.

NOTE: the partition problem is considered "the easiest NP-hard problem". So, while "few nonzeros" is NP-hard, it may still be easy in practice. Alternatively, it may be possible to reduce to "few nonzeros" from a harder NP-hard problem. So its exact hardness is still open.