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.
Best Answer
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.