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 can be is connected to one 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?

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 can be connected to one 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

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?