<p>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.</p>
<p><strong>Lemma 1.</strong> <em>There is a parsimonious poly-time reduction from 3-SAT to 1-in-3-SAT.</em></p>
<p>Note: This reduction comes originally from [1].  [2] points out that it is parsimonious.</p>
<p>[1] Schaefer, Thomas J. <a href="https://doi.org/10.1145/800133.804350" rel="noreferrer">The complexity of satisfiability problems</a>, 1978, Proceedings of the tenth annual ACM symposium on Theory of computing.</p>
<p>[2] V. Bura. <a href="https://arxiv.org/pdf/1808.02821v1.pdf" rel="noreferrer">A Kernel Method for Positive 1-in-3-SAT</a>.  draft on arXiv.org.</p>
<p><em>Proof sketch.</em>  Given any 3-SAT instance <span class="math-container">$\Phi$</span>, obtain <span class="math-container">$\Phi'$</span> from <span class="math-container">$\Phi$</span> by replacing each clause <span class="math-container">$x \vee y \vee z$</span> by the clauses <span class="math-container">$(\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)$</span>, where <span class="math-container">$u_1, u_2, u_3, u_4$</span> are new variables specific to this clause.  The satisfying assignments for <span class="math-container">$\Phi$</span> then correspond bijectively to assignments for the modified formula <span class="math-container">$\Phi'$</span> such that exactly one literal in each clause is true. <span class="math-container">$~~~\Box$</span></p>
<p>For example, in an assignment for <span class="math-container">$\Phi$</span> that makes <span class="math-container">$x$</span> and <span class="math-container">$y$</span> true and <span class="math-container">$z$</span> false, the corresponding assignment for <span class="math-container">$\Phi'$</span> would extend that assignment by taking <span class="math-container">$u_1$</span> to be true, and <span class="math-container">$u_2, u_3, u_4$</span> to be false.</p>
<p>Next define 1+3DM to be the following variant of 3DM.  The input <span class="math-container">$(X,Y,Z,T,S)$</span> consists of three pairwise-disjoint sets <span class="math-container">$X, Y, Z$</span> each containing <span class="math-container">$n$</span> <em>elements</em>, a collection of triples <span class="math-container">$T \subseteq X\times Y \times Z$</span>, and a collection of <em>singletons</em> <span class="math-container">$S\subseteq X \cup Y \cup Z$</span>. 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.</p>
<p><strong>Lemma 2.</strong> <em>There is a parsimonious reduction from 1-in-3-SAT to 1+3DM.</em></p>
<p><em>Proof sketch.</em>  Given a 1-in-3-SAT formula <span class="math-container">$\Phi$</span>, the reduction produces the following instance of 1+3DM.</p>
<p>For every variable <span class="math-container">$a$</span> in <span class="math-container">$\Phi$</span>, let <span class="math-container">$k$</span> be the number of occurrences of <span class="math-container">$a$</span> in <span class="math-container">$\Phi$</span>.  Build a variable gadget of &quot;size&quot; <span class="math-container">$k$</span> as follows.  First, create <span class="math-container">$4k$</span> new elements <span class="math-container">$a_1, a_2, \ldots, a_k$</span>, and <span class="math-container">$\overline a_1, \overline a_2, \ldots, \overline a_k$</span>, and <span class="math-container">$y_1, y_2, \ldots, y_k$</span> and <span class="math-container">$z_1, z_2, \ldots, z_k$</span>.  For each <span class="math-container">$i\in\{1,2,\ldots, k\}$</span> add triples <span class="math-container">$(a_i, y_i, z_i)$</span> and <span class="math-container">$(\overline a_i, y_i, z_{i-1})$</span>, interpreting <span class="math-container">$z_0$</span> as <span class="math-container">$z_k$</span>.  Here's an illustration for <span class="math-container">$k=3$</span>:</p>
<p><span class="math-container">$~~~$</span><a href="https://i.sstatic.net/rY5b7l.jpg" rel="noreferrer"><img src="https://i.sstatic.net/rY5b7l.jpg" alt="enter image description here" /></a></p>
<p>Note that in any solution either the <span class="math-container">$k$</span> triples of the form <span class="math-container">$(a_i, y_i, z_i)$</span> must be chosen, or the <span class="math-container">$k$</span> triples of the form <span class="math-container">$(\overline a_i, y_i, z_{i-1})$</span> must be chosen.  Hence, either all <span class="math-container">$k$</span> <span class="math-container">$a_i$</span>'s are left uncovered, or all <span class="math-container">$k$</span> <span class="math-container">$\overline a_i$</span>'s are left uncovered.</p>
<p>For every clause create a &quot;clause gadget&quot; as follows.  We'll illustrate the construction by example.  For the clause <span class="math-container">$a\vee \overline b \vee c$</span> in <span class="math-container">$\Phi$</span>, select elements <span class="math-container">$a_h$</span>, <span class="math-container">$\overline b_i$</span>, <span class="math-container">$c_j$</span> (one for each literal in the clause), from the previously created variable gadgets, where the indices are chosen so that the clause contains the <span class="math-container">$h$</span>th, <span class="math-container">$i$</span>th, and <span class="math-container">$j$</span>th occurrences of the variables <span class="math-container">$a$</span>, <span class="math-container">$b$</span>, and <span class="math-container">$c$</span>, respectively, in <span class="math-container">$\Phi$</span>.
Create two new nodes <span class="math-container">$y,z$</span>.
Add three triples <span class="math-container">$(a_h, y, z)$</span>, <span class="math-container">$(\overline b_i, y, z)$</span>, and <span class="math-container">$(c_j, y, z)$</span>:</p>
<p><span class="math-container">$~~~$</span><a href="https://i.sstatic.net/dlT3pl.jpg" rel="noreferrer"><img src="https://i.sstatic.net/dlT3pl.jpg" alt="enter image description here" /></a></p>
<p>Finally add three elements <span class="math-container">$\overline a_h$</span>, <span class="math-container">$b_i$</span>, and <span class="math-container">$\overline c_j$</span> (for the complements of the literals in the clause) to the set of singletons <span class="math-container">$S$</span>.  These &quot;singleton&quot; 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 <span class="math-container">$a$</span>, among each pair of elements <span class="math-container">$a_i$</span> and <span class="math-container">$\overline a_i$</span> in the variable gadget, one of <span class="math-container">$a_i$</span> or <span class="math-container">$\overline a_i$</span> occurs in a triple in any clause gadget, while the other does not and is an allowed singleton.</p>
<p>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.</p>
<p>This completes the reduction.
To verify that it is correct, consider any 1-in-3 satisfying assignment <span class="math-container">$A$</span> for <span class="math-container">$\Phi$</span>.  The corresponding matching uses the following triples.  For each variable <span class="math-container">$a$</span> that is true, use the triples of the form <span class="math-container">$(\overline a_i, y_i, z_{i-1})$</span> to cover all elements in the variable gadget except the <span class="math-container">$a_i$</span>'s; also, for each element <span class="math-container">$a_i$</span> that is not used in any clause gadget, choose <span class="math-container">$a_i$</span> as a singleton.
For each variable <span class="math-container">$a$</span> that is false, use the triples of the form <span class="math-container">$(a_i, y_i, z_i)$</span> to cover all the elements of the variable gadget except the <span class="math-container">$\overline a_i$</span>'s; also, for each element <span class="math-container">$\overline a_i$</span> that is not used in any clause gadget, choose <span class="math-container">$\overline a_i$</span> as a singleton.
For each clause, e.g., <span class="math-container">$a\vee \overline b \vee c$</span>, select the true literal, and use the triple from the clause gadget that contains that literal.  E.g. if <span class="math-container">$a$</span> is true, use the triple <span class="math-container">$(a_i, y, z)$</span> from the clause gadget.</p>
<p>The above correspondence is a bijection between 1-in-3 assignments to <span class="math-container">$A$</span> and valid matchings, so the reduction is correct.</p>
<p>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. <span class="math-container">$~~~\Box$</span></p>
<p><strong>Lemma 3.</strong> <em>There is a parsimonious reduction from 1+3DM to 3DM.</em></p>
<p><em>Proof idea.</em> Given any instance <span class="math-container">$(X, Y, Z, T, S)$</span> of 1+3DM, the reduction outputs the instance <span class="math-container">$(X', Y', T')$</span> of 3DM obtained as follows.</p>
<p>Create three copies of each of <span class="math-container">$(X, Y, Z, T)$</span>, with all copied elements distinct.
Label them <span class="math-container">$(X_1, Y_1, Z_1, T_1)$</span>, <span class="math-container">$(X_2, Y_2, Z_2, T_2)$</span>, and <span class="math-container">$(X_3, Y_3, Z_3, T_3)$</span>.
Let <span class="math-container">$X'=X_1 \cup Y_2 \cup Z_3$</span>, and <span class="math-container">$Y'= X_2 \cup Y_3 \cup Z_1$</span>, and <span class="math-container">$Z'=X_3\cup Y_1 \cup Z_2$</span>.
Let <span class="math-container">$T' = T_1 \cup T_2 \cup T_3 \cup S'$</span> where
<span class="math-container">$$S' = \big\{\{s_1, s_2, s_3\} : s \in S\big\},$$</span>
where <span class="math-container">$s_1$</span>, <span class="math-container">$s_2$</span>, and <span class="math-container">$s_3$</span> are the three copies of element <span class="math-container">$s$</span>
(that is, <span class="math-container">$s_i$</span> is the copy of <span class="math-container">$s$</span> that occurs in <span class="math-container">$X_i \cup Y_i \cup Z_i$</span>).</p>
<p>Given any (1+3D) matching <span class="math-container">$M$</span> for <span class="math-container">$(X, Y, Z, T, S)$</span>, the corresponding matching for <span class="math-container">$(X', Y', Z', T')$</span> is obtained by choosing, for every triple <span class="math-container">$(x, y, z)$</span> in <span class="math-container">$M$</span>, the three corresponding triples in <span class="math-container">$T'$</span>,
namely <span class="math-container">$(x_1, y_1, z_1)$</span>, <span class="math-container">$(y_2, x_2, z_2)$</span>,  and <span class="math-container">$(z_3, y_3, x_3)$</span>,
along with a triple <span class="math-container">$(s_1, s_2, s_3)$</span> for each singleton <span class="math-container">$s$</span> in <span class="math-container">$M$</span>.
This correspondence is bijective because of the technical assumption that the chosen singletons determine the matching <span class="math-container">$M$</span>. <span class="math-container">$~~~~\Box$</span></p>

CC BY-SA 4.0
2020-08-31T18:01:29.463Z
2020-08-31T18:49:47.790Z
2020-08-31T18:49:47.790Z
Neal Young
<p>In <a href="https://youtu.be/CIsfsGGOmKI?t=1075" rel="noreferrer">this talk</a> at the Simons Institute, Holger Dell notes that there is a parsimonious reduction from 3-SAT to the <a href="https://en.wikipedia.org/wiki/3-dimensional_matching" rel="noreferrer">3-dimensional Matching</a> (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.</p>
<p>My question then, is <strong>what is an example of a parsimonious reduction from 3-SAT to 3-DM?</strong></p>
<p><strong>Additional Context:</strong>
The only reduction from 3-SAT to 3-DM I know of is the one presented in Garey &amp; Johnson's <em>Computers and Intractability</em> (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.</p>
<p>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.</p>
<p>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?</p>

<cc.complexity-theory><np-hardness><counting-complexity><reductions><matching>
Why is the reduction from 3-SAT to 3-dimensional Matching Parsimonious?
Naysh
# Why is the reduction from 3-SAT to 3-dimensional Matching Parsimonious?

(Asked by: username_0 on 2020-08-30)

In [this talk](https://youtu.be/CIsfsGGOmKI?t=1075) at the Simons Institute, Holger Dell notes that there is a parsimonious reduction from 3-SAT to the [3-dimensional Matching](https://en.wikipedia.org/wiki/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?

**Tags:** cc.complexity-theory, np-hardness, counting-complexity, reductions, matching

---

## 1 answers

### Answer by username_1 on 2020-08-31. Score: 15 | Accepted answer

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](https://doi.org/10.1145/800133.804350), 1978, Proceedings of the tenth annual ACM symposium on Theory of computing.

[2] V. Bura. [A Kernel Method for Positive 1-in-3-SAT](https://arxiv.org/pdf/1808.02821v1.pdf). 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](https://i.sstatic.net/rY5b7l.jpg)](https://i.sstatic.net/rY5b7l.jpg)

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](https://i.sstatic.net/dlT3pl.jpg)](https://i.sstatic.net/dlT3pl.jpg)

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$


---

