# Is that particular case of the “minimum weight solution to linear equations” still NP-complete?

We in our research group are working in the application of heuristic methods to the inverse illumination problem (that is, given a set of constraints about the illumination conditions in a scene, find the places where the light sources have to be placed and their intensities in order to fulfill the constraints and minimize the cost). We would like to justify the use of heuristic methods by proving the problem to be NP-hard and we have found it to be closely related to the "minimum weight solution to linear equations" (MWSLE) NP-complete problem of Garey and Johnson's "Computers and intractability", with the particularity that, given that light source emittances can not be negative, the solution to the linear equations system has to be formed only by non-negative values. Summarizing, the problem is the following:

MINIMUM WEIGHT POSITIVE SOLUTION TO LINEAR EQUATIONS.

INSTANCE: Finite set $X$ of pairs $(\vec{x},b)$, where $\vec{x}$ is an m-tuple of non-negative integers and $b$ is a non-negative integer, and a positive integer $K \leq m$.

QUESTION: Is there an m-tuple $\vec{y}$ of non-negative rational entries such that $\vec{y}$ has at most $K$ non-zero entries and such that $\vec{x} \cdot \vec{y}=b$ for all $(\vec{x},b)\in X$?

Garvey and Johnson state that MWSLE's NP-completeness can be proved from the "exact covering by 3-sets" problem but don't give more details. Exact cover by 3-sets is a natural generalization of the perfect matching problem to hypergraphs G=(V,E) with all edges e∈E containing 3 vertices (instead of 2) and |V| is divisible by 3. The problem is to find a subset of the hyperedges such that each vertex is incident to exactly one of the selected hyperedges.

We are trying to prove that the restricted problem is still NP-complete but we don't see the way to do it. Any clues?

Esteve

• Please add a definition of exact cover by 3-sets to your post so people don't have to look it up in Garey and Johnson (page 221) themselves. – Warren Schudy Dec 10 '10 at 21:16
• Done. I included the definition you provided in your answer. – esteve Dec 14 '10 at 13:39

Here's a sketch of an NP-hardness proof. Exact cover by 3-sets is a natural generalization of the perfect matching problem to hypergraphs $G=(V,E)$ with all edges $e \in E$ containing 3 vertices (instead of 2) and $|V|$ is divisible by 3. The problem is to find a subset of the hyperedges such that each vertex is incident to exactly one of the selected hyperedges. Let $x_e$ be a 0/1 variable for each hyperedge $e$ indicating whether or not it is used. Clearly the system of equations
$\sum_{e \in E : v \in e} x_e = 1$ for all $v \in V$
has only non-negative coefficients and has a solution with at most $|V|/3$ positive coefficients if $G$ has an exact cover. The other direction, namely showing that this system has such a solution only if $G$ has an exact cover, is less trivial but still easy.
• It was easy, indeed. If the system has a solution then the edges corresponding to the $\frac{|V|}{3}$ positive coefficients form an exact covering for the graph. Every equation must contain at least a positive coefficient, so all the vertices will belong to the covering. On the other hand the covering will have only $3\cdot\frac{|V|}{3}$ vertices, so it will be an exact covering. – esteve Dec 14 '10 at 11:57