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&lt;n$.

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.