Solving an LP with at most m-1 nonzeros
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.