1
$\begingroup$

I've been reading about the standard reduction from 3sat to 3DM and my question was regarding the 'clean up gadgets'. So suppose i take an instance of 3-Sat with $n$ variables and $k$ clauses. Once we have constructed the reduction it says we need to add an extra $(n-1)k$ clean up gadgets for the remaining uncovered tips.

My question is if we were actually trying to solve the problem using this polynommial time reduction to a 3-dimensional matching, surely we wouldn't know which tips are free until we have actually found a matching for the clause gadgets and so have used $k$ tips-one for each of the clauses, then allowing us to match the remaining $(n-1)k$ tips.

$\endgroup$
  • $\begingroup$ Can you point us to or describe the specific version of the reduction you are referring to? $\endgroup$ – Clement C. Jun 4 '15 at 20:21
  • $\begingroup$ I'm referring to the reduction used in these notes i think it starts around page 47 courses.cs.vt.edu/cs5114/spring2009/lectures/… $\endgroup$ – Pavan Sangha Jun 4 '15 at 22:53
  • $\begingroup$ They mention using clean up gadgets just not how they use them. $\endgroup$ – Pavan Sangha Jun 4 '15 at 22:53
1
$\begingroup$

There are 6 tips associated with each clause $C = x_a \lor x_b \lor x_c$. They represent $x_a$, $\overline{x_a}$, $x_b$, $\overline{x_b}$, $x_c$, and $\overline{x_c}$. 3 of them (one from each pair) will be covered by matches from the TF-ring for that variable. 1 of them will be covered by the clause match. That leaves 2 uncovered tips from the original 6 tips associated with the clause, and they require cleaning up.

This is easily done. You create 4 nodes, $q_1,q_2,q_3,q_4$. Create 6 potential matches, $(q_1,q_2,x_a)$, $(q_1,q_2,\overline{x_a})$, $(q_1, q_2, x_b)$... and 6 more potential matches $(q_3,q_4,x_a)$, $(q_3,q_4,\overline{x_a})$... Now it will always be possible to cover the two unused tips. You could actually get away with 8 matches instead of 12 if you're clever.

Or if you wanted to be stingy with the nodes you could just allocate one of them, $q$, and create 12 matches that cover all the possibilities for leftover nodes: $(q,x_a,x_b)$, $(q, x_a, \overline{x_b})$, $(q, \overline{x_a}, x_b)$, etc.

$\endgroup$
  • $\begingroup$ Sorry is your explanation related to the reduction that is in the notes that i attached? $\endgroup$ – Pavan Sangha Jun 5 '15 at 14:13
  • $\begingroup$ You make $(n-1)k$ cleanup gadgets, but each of them can clean up an unused tip from any of the $n$ variables. The choice of which cleanup gadget cleans up which tip is part of solving the 3DM problem, not something done beforehand. $\endgroup$ – NovaDenizen Jun 5 '15 at 16:02
  • $\begingroup$ Ok thanks, that's what i thought $\endgroup$ – Pavan Sangha Jun 5 '15 at 21:17
  • $\begingroup$ Just want to add the general reasoning of the first paragraph as to how it's $(n-1)k$ tips. Since $k$ clauses introduce $2k$ tips and there are $n$ gadgets, there are a total of $2nk$ tips. Half of them will be covered by covering the cores(TF-triples), and each clause gadget covers one tip, so there are $\frac{2nk}{2} - k = (n-1)k$ tips left that need cleaning up. $\endgroup$ – RexYuan Mar 6 '18 at 17:09

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.