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

<p>$\sum_{e \in E : v \in e} x_e = 1$    for all $v \in V$
</p>

<p>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 <em>only if</em> $G$ has an exact cover, is less trivial but still easy.</p>

CC BY-SA 2.5
2010-12-13T10:59:57.057Z
Thanks a lot for your quick and kind answer. I'm now struggling with the less trivial but easy part. Regards.
esteve
CC BY-SA 2.5
2010-12-14T11:57:38.937Z
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
CC BY-SA 2.5
2010-12-10T21:23:17.723Z
2010-12-10T21:28:19.733Z
2010-12-10T21:28:19.733Z
Warren Schudy
<p>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:</p>

<hr>

<p>MINIMUM WEIGHT POSITIVE SOLUTION TO LINEAR EQUATIONS.</p>

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

<p>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$?</p>

<hr>

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

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

<p>Thanks in advance</p>

<p>Esteve</p>

CC BY-SA 2.5
2010-12-10T21:16:34.543Z
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
CC BY-SA 2.5
2010-12-14T13:39:19.300Z
Done. I included the definition you provided in your answer.
esteve
<cc.complexity-theory><np-hardness><cg.comp-geom><application-of-theory>
Is that particular case of the "minimum weight solution to linear equations" still NP-complete?
esteve
# Is that particular case of the "minimum weight solution to linear equations" still NP-complete?

(Asked by: username_0 on 2010-12-10)

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?

Thanks in advance

Esteve

**Tags:** cc.complexity-theory, np-hardness, cg.comp-geom, application-of-theory
> **Comments:**
> **username_1**: 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.  
> **username_0**: Done. I included the definition you provided in your answer.  

---

## 1 answers

### Answer by username_1 on 2010-12-10. Score: 5 | Accepted answer

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.

> **Comments:**
> **username_0**: Thanks a lot for your quick and kind answer. I'm now struggling with the less trivial but easy part. Regards.  
> **username_0**: 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.  

---

