8
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Warren Schudy Dec 10 '10 at 21:16
  • $\begingroup$ Done. I included the definition you provided in your answer. $\endgroup$ – esteve Dec 14 '10 at 13:39
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks a lot for your quick and kind answer. I'm now struggling with the less trivial but easy part. Regards. $\endgroup$ – esteve Dec 13 '10 at 10:59
  • $\begingroup$ 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. $\endgroup$ – esteve Dec 14 '10 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.