# reduction from 3sat to 3 dimensional matching.

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.

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

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.
• 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. – NovaDenizen Jun 5 '15 at 16:02
• 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. – RexYuan Mar 6 '18 at 17:09