[Math] Is this problem solvable in polynomial time

algorithmscomputational complexity

Let's start with a picture: http://i.imgur.com/P1k8T.png
What you see here are boxes and circles inside the boxes. Each circle is connected to zero or more boxes. One box is the primary box, it's the grey one. Here is another example (the top box is the primary box): http://i.imgur.com/ibOIO.png (I apologize for the crappy drawings).

The goal is to select a subset of all circles such that:

  1. If a circle is selected, then all the boxes it is connected to must be selected.
  2. If a box is selected then one of the circles in it must be selected.
  3. The primary box is selected.
  4. The sum of the numbers in the selected circles is minimal.

In the top picture the optimal selection of circles has been colored blue. In the bottom picture there are two optimal solutions: select the 3 in the top box and the 1 in the right box. Other solution: select the 2 in the top box, the 1 in the left box and the 1 in the right box.

My question is: is this solvable in polynomial time, or if not is it possible to approximate it? If the graph is tree structured then dynamic programming can solve the problem, but diamond structures seem to complicate the problem.

I have asked this problem on stackoverflow.com, but that doesn't seem to get very far and I thought maybe this is a more appropriate place?

Best Answer

There is a straightforward encoding of 3-SAT into this problem, which means that unless P=NP, no, there cannot be a polynomial-time algorithm that solves it. The encoding can be constructed as follows. Given a formula $\phi=\psi_1\wedge\dots\wedge\psi_k$ in conjunctive normal form over propositional variables $v_1,\dots,v_n$, you have the following boxes:

  1. For each $v_i$, two boxes $A_i, B_i$ representing the literals $v_i$ and $\neg v_i$. Both contain a single unit-weight circle.
  2. Also for each $v_i$, a box $C_i$ representing the law of the excluded middle: This box contains two circles with weight 0, one connected to $A_i$, the other to $B_i$.
  3. For each clause $\psi_j=l_1\vee l_2 \vee l_3$, a box $D_j$ containing three weight-0 circles connected to the corresponding $A_i$ or $B_i$.
  4. The root box, containing a single weight-0 circle connected to all the $C_i$ and $D_j$.

This can be done in time linear in the size of $\phi$.

Then a set of circles satisfying your constraints must contain at least one of $A_i,B_i$ for all $i$, and has weight $n$ if and only if it corresponds to a valid valuation of the $v_i$ which satisfies $\phi$. In particular, satisfiability of $\phi$ can be decided by checking if the minimum weight solution has weight $n$.

Related Question