Simple (?) NP-hard reduction

Question

Let $RLS(k)$ be the problem where we try to determine whether a Linear System of $n$ unknown variables and $m$ equations with Rational coefficients, has a $k$-solution which is basically a vector $x= (x_1, x_2, \dots, x_n)$ such that at most $k$ of the $x_i$'s are non-zero.

Prove that $RLS(k)$ is NP-hard

---

I am trying to reduce Vertex Cover ($VC$) to $RLS(k)$.

My idea was that starting with a graph $G(V,E)$ then one can encode each edge $(x_i, x_j)$ as $x_i + x_j \neq 0$. Reason being, if $x_i = 0$ we want $x_j \neq 0$ (i.e. if we don't "choose" vertex i for our VC then we are forced to "choose" node j for the $VC$).

We conclude, that this System has a $k$-solution iff $G$ has a Vertex Cover of size $\leq k$

Of course, the issue is that the above is NOT a system of equations but rather a system of inequalities.

I also thought about introducing dummy variables but that didn't me lead anywhere either.

Is this even the correct reduction for this type of problem? Are there any other common reductions that could potentially be straightforward? My intuition tells me that (due to the $k$-restriction) Vertex Cover and Independent Set are probably the easiest ones. Thoughts?

Update/Note: I am quite comfortable with this topic, so I am looking for some brainstorming with a fruitful discussion, and not necessarily a solution. So don't be afraid to share even "partial" ideas.

Answer 1

We can reduce 1-IN-3SAT (that is, 3SAT with the condition that in each clause, exactly one literal is true) to $RLS(k)$ as follows:

Suppose that we have a 1-IN-3SAT formula in $n$ variables $\{b_1, \dots, b_n\}$.

• For each boolean variable $b_i$, define two rational variables $x_i$ and $x_i'$ and add the constraint $x_i + x_i' = 1$.
• For a clause with positive literals $\{b_i, b_j, b_k\}$, add the constraint $x_i + x_j + x_k =1$.
• When a negative literal $\neg b_i$ occurs in a clause, use $x_i'$ instead of $x_i$.
• Require that at most $n$ rational variables (out of $2n$) can be nonzero.

From the constraint $x_i + x_i' = 1$, we know that at least one of $x_i$ and $x_i'$ has to be nonzero for every $i,$ which is already $n$ nonzero variables. That means exactly one of $x_i$ and $x_i'$ can be nonzero, which means either $x_i = 1$ and $x_i' = 0$, or $x_i = 0$ and $x_i' = 1$. Interpret this as a truth assignment for $b_i$: $x_i = 1 \; \Longleftrightarrow \; b_i$ and $x_i' = 1 \; \Longleftrightarrow \; \neg b_i$. Then the constraint we use for each clause is equivalent to saying that exactly one literal in the clause is true.

Therefore a solution to the rational linear system produces a satisfying assignment to the 1-IN-3SAT formula.