Embedding SATISFIABILITY into 3-DIMENSIONAL MATCHING

Question

Using the fact that the satisfiability problem is NP Complete, demonstrate that the 3-Dimensional Matching problem is NP Complete.

I am currently in need of clarification of the proof of the above statement as given in the Combinatorial Optimization text by Papadimitriou and Steiglitz. I am a graduate student in mathematics currently finishing my dissertation, and one of my chapters includes a citation and quote of this result, and a clear understanding of it has so far escaped me. In order to minimize the inevitable wall of text, I will summarize the proof as briefly as possible.

The authors reduce SATISFIABILITY to instances of 3-DIMENSIONAL MATCHING as follows: given a Boolean formula $F$ with clauses $C_1, \ldots, C_m$ over literals $x_1, \ldots, x_n,$ the sets $$U=\{x_i^j, \bar{x}_i^j\},i \in [n], j \in [m],$$

$$V=\{a_i^j\}\cup\{v_j\}\cup\{c_i^j\}, $$ and $$W=\{b_i^j\}\cup\{w_j\}\cup\{d_i^j\}, i \in [n-1], j \in [m]$$ are constructed, with $i \in [n]$ for the $a$ and $b$ elements and $i \in [n-1]$ for the $c$ and $d$ elements and $j \in [m]$ as before. I noted that $|U|=|W|=|V|=2mn$ to verify identical cardinality of these three sets.

The triplet set $$T=\{(x_i^j, a_i^j, b_i^j)\} \cup \{(\bar{x}_i^j, a_i^{j+1}, b_i^j)\} \cup \{(\lambda_j, v_j, w_j)\} \cup \{(\lambda_k, c_i^j, d_i^j)\}$$ is then constructed, where $i \in [n], j \in [m]$ in the first three sets of this union and $i \in [n-1], j \in [m], k \in [m]$ in the fourth set in this union. It is stated that $\lambda_j$ in the third set in this union are literals in $C_j;$ the $\lambda_k$ in the fourth set in this union are simply identified as literals.

First, we assume that a subset $S \subset T$ exists such that each element of $U,$ $V,$ and $W$ appears in exactly one triplet in $S.$ Because of the definition of $T$ and these constraints on $S,$ we know that at least $mn$ triplets of the first two sets listed in the representation for $T$ appear in $S$; because no pair in $S$ can match elementwise, it follows that exactly $mn$ elements are chosen from these "a,b" triplets, since for each $i,$ exactly one of $x_i^j$ or $\bar{x}_i^j$ are present in triplets of $S$ for all $j$ (supposing not, the construction of $T$ forces a match in the $a$ position or the $b$ position). The proof declares $x_i$ to be false if $x_i$ is chosen, and if $\bar{x}_i$ is instead chosen then $x_i$ is true (so that $\bar{x}_i$ is false).

The proof goes on to explain that the third and fourth set in the union definition of $T$ must therefore comprise the remaining $mn$ elements to be selected for $S.$ Since all $m$ elements of the third set comprise exactly one literal $\lambda_j$ in each clause $C_j,$ and since the first $mn$ choices from the first two sets in the union for $T$ were all assumed false, then, since $\lambda_j$ cannot match the $x_i^j$ or $\bar{x}_i^j$ as selected for the $a,b$ triplets in the position $i$ to which $\lambda_j$ corresponds, then $\lambda_j$ must be a true literal in the clause $j.$ Since such a selection exists for all $m$ clauses, the third set of $T$ (which, again, must be included in $S$) represents a truth setting that satisfies $F.$ The fourth set is labeled as a "garbage set" that picks up the rest of the literals.

The other direction, assuming that a given $F$ is satisfiable, is easy: make the same construction as above and simply select the $\lambda_j$ to correspond to the truth setting that satisfies $F,$ set the $a, b$ triplets opposite these settings in these positions, and you've constructed a $T$ that has a perfect matching subset $S$ following the above rubric. This direction is direct and is not the point of concern, nor is there any concern with showing the problem is in NP.

What my advisor finds troublesome is the first direction. His challenge is that if we happen to construct a $T$ that does not have a perfect matching subset $S$ as given above, he cannot see how we can conclude that $F$ is not satisfiable; the third subset in the union for $T$ may just happen to be a truth setting that doesn't work for $F,$ and we do not know from this fact whether or not some other formulation of $T$ exists with a "truth setting" subset that actually satisfies $F.$ I am not aware how to answer his challenge to this proof; I have attempted to explain that the rubric for proving NP-Completeness allows us to assume that the $T$ we constructed has a perfect matching subset $S,$ but he continues to answer that if we did not have such a subset for the $T$ we constructed, we would not know for sure whether $F$ is unsatisfiable or not. In short, he believes that a "no" answer for 3-Dimensional-Matching must imply a "no" answer for the transferred satisfiability problem. Is that something that must be demonstrated in proofs of NP-Completeness?

The other question I had is one of my own. For our selection of the first $mn$ elements for the matching subset $S,$ the proof explains that, for each $i,$ we freely select exactly one of $x_i$ or $\bar{x}_i$ for every $j,$ but not both, and furthermore we can freely declare these $n$ selections all false. I do not see how we are "free" to make such selections - for example, if $F$ happens to be, in every clause, exactly what we selected for these first $mn$ "false" elements, then the $m$ elements from the third set of $T$ that are supposed to be the truth setting variables cannot possibly correspond to the literals in any of the $m$ clauses, but we can construct $S$ nonetheless. I suppose I am getting confused with what the author of this proof meant by "choosing" exactly one of $x_i$ or $\bar{x}_i$ for every $j,$ but I can't identify the point where my understanding breaks down.

Any help clarifying these questions would be deeply appreciated!

Answer 1

To answer your following question:

In short, he believes that a "no" answer for 3-Dimensional-Matching must imply a "no" answer for the transferred satisfiability problem. Is that something that must be demonstrated in proofs of NP-Completeness?

Yes, this must definitely hold for your construction. Note however, that it is already proven in the following paragraph (assuming the proof is correct, I did not verify that)

The other direction, assuming that a given $F$ is satisfiable, is easy: make the same construction as above and simply select the $λ_j$ to correspond to the truth setting that satisfies $F$, set the $a,b$ triplets opposite these settings in these positions, and you've constructed a $T$ that has a perfect matching subset $S$ following the above rubric. This direction is direct and is not the point of concern, nor is there any concern with showing the problem is in NP.

Here it is shown that if $F$ is satisfiable, $T$ has a correct matching subset. By contraposition, if $T$ does NOT have such a subset, $F$ cannot be satisfiable.

EDIT: Let me try to answer your second question as well:

I suppose I am getting confused with what the author of this proof meant by "choosing" exactly one of $x_i$ or $\bar{x}_i$ for every $j$, but I can't identify the point where my understanding breaks down.

This direction of the proof shows how, given a matching in $T$, you can construct a satisfying solution in $F$ (thus showing it is satisfiable).

You do indeed not randomly (or, indeed, freely) choose such an $x_i$. Instead, (I do not know if the book shows this clearer then your summary) you demonstrate that a matching S must have a certain format (i.e. it contains exactly one of the sets $\{x_i^j,a_i^j,b_i^j\}$ or $\{\bar{x}_i^j,a_i^j,b_i^j\}$). Having this knowledge, we now construct the solution for $F$ by saying we choose $x_i := false$ if $\{x_i^j,a_i^j,b_i^j\} \in S$ and $x_i:=true$ otherwise (note that this is indeed a choice we make, it just happens to be a clever one). Then, you can show this is a satisfying solution: If it were not, there would be a clause $C_j$ for which all literals are set to $false$. But then there is no way to cover $v_j$ by our matching $S$ ($v_j$ needs to be covered by set $\{\lambda_j,v_j,w_j\}$, but all $\lambda_j$ are already matched in $S$), which is a contradiction.

EDIT: It appears the construction of $T$ is not clear, let me try give an example of (what I believe) the construction should look like. Suppose $F = (x_1 \vee x_2 \vee x_3) \wedge (x_1 \vee \bar{x}_2 \vee \bar{x}_3)$ , so $n = 3$ and $m=2$. Construct variables

• $U = \{x_1^1, \bar{x}_1^1, x_1^2, \bar{x}_1^2, x_2^1, \bar{x}_2^1, x_2^2, \bar{x}_2^2,x_3^1, \bar{x}_3^1, x_3^2, \bar{x}_3^2\}$
• $V = \{a_1^1, a_1^2, a_2^1,a_2^2, a_3^1,a_3^2\} \cup \{v_1, v_2\} \cup \{c_1^1, c_2^1,c_1^2, c_2^2\}$
• $W = \{b_1^1, b_1^2, b_2^1,b_2^2, b_3^1,b_3^2\} \cup \{w_1, w_2\} \cup \{d_1^1, d_2^1,d_1^2, d_2^2\}$

Then add all following triples to $T$:

• $\{x_i^j, a_i^j, b_i^j\}$ for all $i \in [3]$ and $j \in 2$ (this adds six triplets)
• $\{\bar{x}_i^j, a_i^j, b_i^j\}$ for all $i \in [3]$ and $j \in 2$ (this adds six more triplets)
• For each literal $\lambda \in C_j$ add $\{\lambda^j, v_j,w_j\}$, in our example: $\{x_1^1,v_1,w_1\},\{x_2^1,v_1,w_1\},\{x_3^1,v_1,w_1\},\{x_1^2,v_2,w_2\},\{\bar{x}_2^2,v_1,w_1\},\{\bar{x}_3^2,v_1,w_1\}$ Note that I assume nothing about the satisfiability of $F$ (or of the satisfying assignment that $F$ does/does not have).
• For each possible $x \in U$ and all $i \in [n-1],j\in [m]$ the triples $\{x,c_i^j,d_i^j\}$.