12
$\begingroup$

In this talk at the Simons Institute, Holger Dell notes that there is a parsimonious reduction from 3-SAT to the 3-dimensional Matching (3-DM) problem. In other words, there is a reduction between these two problems that also works as a reduction from counting satisfying assignnments to counting 3-dimensional matchings.

My question then, is what is an example of a parsimonious reduction from 3-SAT to 3-DM?

Additional Context: The only reduction from 3-SAT to 3-DM I know of is the one presented in Garey & Johnson's Computers and Intractability (page 50, theorem 3.2). That reduction involves composing certain variable gadgets, clause gadgets, and garbage collection gadgets. Roughly speaking, a satisfying assignment is mapped to a partial matching of vertices in the variable and clause gadgets, and then this partial matching is extended to a full matching using the garbage collection gadgets.

It seems like that reduction ought not to be parsimonious because each satisfying assignment is mapped to a partial matching, and there are many different ways of using the garbage collection to extend this to a full matching. In addition, if a satisfying assignment is chosen that does not set a unique literal to True in each clause, the clause gadgets also seem to have multiple ways to extend the matching.

Is there a way to fix this reduction to be parsimonious? Or is the parsimonious reduction completely different? Or maybe the observations I made in this question are false?

$\endgroup$
13
$\begingroup$

You're right that the standard reduction from 3-SAT to 3D-matching (3DM) is not parsimonious. For the record, here's a sketch of a reduction that is parsimonious. It is obtained by composing parsimonious reductions from 3-SAT to 1-in-3-SAT, from 1-in-3-SAT to a problem we call 1+3DM, and from 1+3DM to 3DM. We sketch each of these next.

Lemma 1. There is a parsimonious poly-time reduction from 3-SAT to 1-in-3-SAT.

Note: This reduction comes originally from [1]. [2] points out that it is parsimonious.

[1] Schaefer, Thomas J. The complexity of satisfiability problems, 1978, Proceedings of the tenth annual ACM symposium on Theory of computing.

[2] V. Bura. A Kernel Method for Positive 1-in-3-SAT. draft on arXiv.org.

Proof sketch. Given any 3-SAT instance $\Phi$, obtain $\Phi'$ from $\Phi$ by replacing each clause $x \vee y \vee z$ by the clauses $(\lnot x \vee u_1 \vee u_2) \wedge (y \vee u_2 \vee u_3) \wedge (\lnot z \vee u_3 \vee u_4)$, where $u_1, u_2, u_3, u_4$ are new variables specific to this clause. The satisfying assignments for $\Phi$ then correspond bijectively to assignments for the modified formula $\Phi'$ such that exactly one literal in each clause is true. $~~~\Box$

For example, in an assignment for $\Phi$ that makes $x$ and $y$ true and $z$ false, the corresponding assignment for $\Phi'$ would extend that assignment by taking $u_1$ to be true, and $u_2, u_3, u_4$ to be false.

Next define 1+3DM to be the following variant of 3DM. The input $(X,Y,Z,T,S)$ consists of three pairwise-disjoint sets $X, Y, Z$ each containing $n$ elements, a collection of triples $T \subseteq X\times Y \times Z$, and a collection of singletons $S\subseteq X \cup Y \cup Z$. The problem is to choose some of the triples and singletons so that each element is in exactly one of the chosen triples or singletons. For technical reasons, we restrict to instances where, for every valid matching (solution), the set of chosen singletons distinctly determines the solution.

Lemma 2. There is a parsimonious reduction from 1-in-3-SAT to 1+3DM.

Proof sketch. Given a 1-in-3-SAT formula $\Phi$, the reduction produces the following instance of 1+3DM.

For every variable $a$ in $\Phi$, let $k$ be the number of occurrences of $a$ in $\Phi$. Build a variable gadget of "size" $k$ as follows. First, create $4k$ new elements $a_1, a_2, \ldots, a_k$, and $\overline a_1, \overline a_2, \ldots, \overline a_k$, and $y_1, y_2, \ldots, y_k$ and $z_1, z_2, \ldots, z_k$. For each $i\in\{1,2,\ldots, k\}$ add triples $(a_i, y_i, z_i)$ and $(\overline a_i, y_i, z_{i-1})$, interpreting $z_0$ as $z_k$. Here's an illustration for $k=3$:

$~~~$enter image description here

Note that in any solution either the $k$ triples of the form $(a_i, y_i, z_i)$ must be chosen, or the $k$ triples of the form $(\overline a_i, y_i, z_{i-1})$ must be chosen. Hence, either all $k$ $a_i$'s are left uncovered, or all $k$ $\overline a_i$'s are left uncovered.

For every clause create a "clause gadget" as follows. We'll illustrate the construction by example. For the clause $a\vee \overline b \vee c$ in $\Phi$, select elements $a_h$, $\overline b_i$, $c_j$ (one for each literal in the clause), from the previously created variable gadgets, where the indices are chosen so that the clause contains the $h$th, $i$th, and $j$th occurrences of the variables $a$, $b$, and $c$, respectively, in $\Phi$. Create two new nodes $y,z$. Add three triples $(a_h, y, z)$, $(\overline b_i, y, z)$, and $(c_j, y, z)$:

$~~~$enter image description here

Finally add three elements $\overline a_h$, $b_i$, and $\overline c_j$ (for the complements of the literals in the clause) to the set of singletons $S$. These "singleton" elements do not occur in any triple in any clause gadget, although they do occur in triples in their respective variable gadgets. Note that, for each variable $a$, among each pair of elements $a_i$ and $\overline a_i$ in the variable gadget, one of $a_i$ or $\overline a_i$ occurs in a triple in any clause gadget, while the other does not and is an allowed singleton.

Note that any solution must choose one of the triples in each clause gadget, thereby covering one of the three elements for the literals in the clause.

This completes the reduction. To verify that it is correct, consider any 1-in-3 satisfying assignment $A$ for $\Phi$. The corresponding matching uses the following triples. For each variable $a$ that is true, use the triples of the form $(\overline a_i, y_i, z_{i-1})$ to cover all elements in the variable gadget except the $a_i$'s; also, for each element $a_i$ that is not used in any clause gadget, choose $a_i$ as a singleton. For each variable $a$ that is false, use the triples of the form $(a_i, y_i, z_i)$ to cover all the elements of the variable gadget except the $\overline a_i$'s; also, for each element $\overline a_i$ that is not used in any clause gadget, choose $\overline a_i$ as a singleton. For each clause, e.g., $a\vee \overline b \vee c$, select the true literal, and use the triple from the clause gadget that contains that literal. E.g. if $a$ is true, use the triple $(a_i, y, z)$ from the clause gadget.

The above correspondence is a bijection between 1-in-3 assignments to $A$ and valid matchings, so the reduction is correct.

The instance meets the technical requirement that, for every valid matching, the set of chosen singletons is distinct. This is because, for each variable, for each occurrence of that variable, the singleton is used iff the corresponding assignment sets the variable so that the literal does not satisfy the clause, so the presence or absence of the singleton determines the value assigned to the variable. So the set of chosen singletons determines the corresponding assignment, which in turn determines the entire matching. $~~~\Box$

Lemma 3. There is a parsimonious reduction from 1+3DM to 3DM.

Proof idea. Given any instance $(X, Y, Z, T, S)$ of 1+3DM, the reduction outputs the instance $(X', Y', T')$ of 3DM obtained as follows.

Create three copies of each of $(X, Y, Z, T)$, with all copied elements distinct. Label them $(X_1, Y_1, Z_1, T_1)$, $(X_2, Y_2, Z_2, T_2)$, and $(X_3, Y_3, Z_3, T_3)$. Let $X'=X_1 \cup Y_2 \cup Z_3$, and $Y'= X_2 \cup Y_3 \cup Z_1$, and $Z'=X_3\cup Y_1 \cup Z_2$. Let $T' = T_1 \cup T_2 \cup T_3 \cup S'$ where $$S' = \big\{\{s_1, s_2, s_3\} : s \in S\big\},$$ where $s_1$, $s_2$, and $s_3$ are the three copies of element $s$ (that is, $s_i$ is the copy of $s$ that occurs in $X_i \cup Y_i \cup Z_i$).

Given any (1+3D) matching $M$ for $(X, Y, Z, T, S)$, the corresponding matching for $(X', Y', Z', T')$ is obtained by choosing, for every triple $(x, y, z)$ in $M$, the three corresponding triples in $T'$, namely $(x_1, y_1, z_1)$, $(y_2, x_2, z_2)$, and $(z_3, y_3, x_3)$, along with a triple $(s_1, s_2, s_3)$ for each singleton $s$ in $M$. This correspondence is bijective because of the technical assumption that the chosen singletons determine the matching $M$. $~~~~\Box$

| cite | improve this answer | |
$\endgroup$

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.