2
$\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$
3
  • $\begingroup$ Can you point us to or describe the specific version of the reduction you are referring to? $\endgroup$
    – Clement C.
    Commented Jun 4, 2015 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$ Commented Jun 4, 2015 at 22:53
  • $\begingroup$ They mention using clean up gadgets just not how they use them. $\endgroup$ Commented Jun 4, 2015 at 22:53

1 Answer 1

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$
4
  • $\begingroup$ Sorry is your explanation related to the reduction that is in the notes that i attached? $\endgroup$ Commented Jun 5, 2015 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$ Commented Jun 5, 2015 at 16:02
  • $\begingroup$ Ok thanks, that's what i thought $\endgroup$ Commented Jun 5, 2015 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
    Commented Mar 6, 2018 at 17:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .