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