8
$\begingroup$

Let's start with a picture: https://i.stack.imgur.com/mEFct.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): https://i.stack.imgur.com/V0mQS.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?

$\endgroup$
1
  • 3
    $\begingroup$ You might be able to get a reasonable solution using loopy belief propagation' approaches (its sometimes also called generalized belief propagation', see en.wikipedia.org/wiki/Belief_propagation). As far as I know, these are approaches to solving dynamic programing type problems when the graphs have cycles. $\endgroup$ Jun 7, 2010 at 4:27

2 Answers 2

12
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ That settles this question. Thanks! $\endgroup$
    – Jules
    Jun 7, 2010 at 17:01
2
$\begingroup$

Not an answer, but this sounds strongly like an and-or evaluation problem. The boxes are OR nodes and the circles are AND nodes, and you're trying to find something like a min-weight satisfying assignment.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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