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_1wedgedotswedgepsi_k$ in conjunctive normal form over propositional variables $v_1,dots,v_n$, you have the following boxes:
- 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.
- 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$.
- For each clause $psi_j=l_1vee l_2 vee l_3$, a box $D_j$ containing three weight-0 circles connected to the corresponding $A_i$ or $B_i$.
- 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$.
No comments:
Post a Comment