Vtyjkyuk

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.

There are 6 tips associated with each clause $C = x_a lor x_b lor x_c$. They represent $x_a$, $overlinex_a$, $x_b$, $overlinex_b$, $x_c$, and $overlinex_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,overlinex_a)$, $(q_1, q_2, x_b)$... and 6 more potential matches $(q_3,q_4,x_a)$, $(q_3,q_4,overlinex_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, overlinex_b)$, $(q, overlinex_a, x_b)$, etc.