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

<ul>
<li>For each <span class="math-container">$j\in[m]$</span>: <span class="math-container">$x_{1j}+x_{2j} = 1$</span></li>
<li>The equal-sum constraint: <span class="math-container">$\sum_{j=1}^m x_{1j} a_j =  \sum_{j=1}^m x_{2j} a_j$</span></li>
</ul>

<p>There always exists a solution with at most <span class="math-container">$m+1$</span> 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. </p>

<p>Now, if we could solve the "few nonzeros" problem, then we could decide whether the above LP has a solution with at most <span class="math-container">$m$</span> 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.</p>

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

CC BY-SA 4.0
2019-01-27T06:29:42.153Z
2019-01-27T06:29:42.153Z
Erel Segal-Halevi
<p>Consider the linear program:</p>

<p><span class="math-container">$$
    A x = b, ~~~~~~ x\geq 0
$$</span>
where <span class="math-container">$A$</span> is an <span class="math-container">$m$</span>-by-<span class="math-container">$n$</span> matrix, <span class="math-container">$x$</span> is an <span class="math-container">$n$</span>-by-1 vector, <span class="math-container">$b$</span> is an <span class="math-container">$m$</span>-by-1 vector, and <span class="math-container">$m&lt;n$</span>.</p>

<p>It is known that, if this program has a solution, then it has a <a href="https://en.wikipedia.org/wiki/Basic_feasible_solution" rel="nofollow noreferrer">basic feasible solution</a>, in which at most <span class="math-container">$m$</span> variables are non-zero.</p>

<p>QUESTION: is there an efficient algorithm to decide whether the LP has a solution in which at most <span class="math-container">$m-1$</span> variables are non-zero, and find it if it exists?</p>

<p>The question is a special case of <a href="https://en.wikipedia.org/wiki/Minimum_relevant_variables_in_linear_system" rel="nofollow noreferrer">Min-RVLS</a> - 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. <a href="https://cstheory.stackexchange.com/q/42171/9453">Finding an additive approximation is hard too</a>. </p>

<p>But, here our goal is much more modest - all we want is to find a solution with one less than the maximum (<span class="math-container">$m$</span>). Is this special case easier?</p>

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

<np-hardness><linear-programming>
Solving an LP with at most m-1 nonzeros
Erel Segal-Halevi
# Solving an LP with at most m-1 nonzeros

(Asked by: username_0 on 2019-01-23)

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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Minimum_relevant_variables_in_linear_system) - 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](https://cstheory.stackexchange.com/q/42171/9453).

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.

**Tags:** np-hardness, linear-programming


---

## 1 answers

### Answer by username_0 on 2019-01-27. Score: 0 | Accepted answer

I think the "few nonzeros" problem is NP-hard, by reduction from the [partition problem](https://en.wikipedia.org/wiki/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.


---

