3-Dimensional Matching $\leq$ $_{p}$ subset sum Explanation

Question

excuse me, could someone explain to me the reduction of the problem 3-dimensional matching to subset sum? I was reading Jon Kleinberg's design algorithms book and when I came across this reduction I didn't understand how it really works:

"So consider an instance of 3-Dimensional Matching specified by sets $X,Y,Z$, each of size n, and a set of m triples $T$ $\subseteq$ $X x Y x Z $. A common way to represent sets is via bit-vector:Each entry in the vector corresponds to a different element, and it holds a 1 if and only if the set contains that element. We adopt this type of approach for representing each triple t = $(x_i,y_j,z_k)$ $\in$ $T$: we construct a number $w_t$ with $3n$ digits that has a 1 in position $i,n+j$ and $2n+k$, and a 0 in all other positions. In other words, for some base $d>1$, $w_t = d^{i-1} +d^{n+j-1}+d^{2n+k-1}$."

To begin with, it is not very clear to me what $X,Y,Z$ sets are or what they represent, as I understand they represent certain digits, but I cannot understand how these inputs work or what they really represent.

In the case of the elements of $T$, according to what I see, they are the elements of the "original" set of Subset Sum represented with vectors.

Now if we wanted to know if in the set A = {1,2,4,10,200}, there is a subset of A whose sum is 16, how could we use the 3dm to represent this example, who would be $X,Y,Z$ and how would it be? represents each number in its vector form?

I'm really stuck with this part. I would really appreciate it if you could help me. Thank you for your consideration.

P.S: I would also greatly appreciate recommendations for other books or resources where the examples of reductions are explained in a little more detail.

Answer 1

When you want to prove a reduction is true (such as this from 3-Dimensional Matching to Subset Sum), what you want to show is that you can take any input for 3-Dimensional Matching and turn it into an input for Subset Sum - not the other way around, as you seem to want.

So, to explain (as it seemed as though you were somewhat uncertain as to how the 3-Dimensional Matching problem is defined): It is an extension of the matching problem in bipartite graphs, only that the graph now is tripartite and each edge consists of three vertices instead of two (i.e. it's a hypergraph). It is known that 3-Dimensional Matching is NP-complete, even with these restrictions:

• Each color class (i.e. $X,Y,Z$) consists of exactly $n$ vertices
• You are tasked to find a matching consisting of $n$ edges (i.e. a perfect matching)
• Every vertex has degree 3 (which implies that the number of edges is exactly $3n$)

As such, you can transform an instance of 3-Dimensional Matching into an instance of Subset Sum by associating each edge with a $3n$-digit number that has a $1$ in the three positions corresponding to the vertices making up the edge, and a 0 everywhere else. You then ask for a subset of the numbers that add up to the number $11\ldots 11$ ($3n$ 1's).

NB: You need to work in base at least 3, if you work in binary it and add together 3 numbers that all have a $1$ in the same position, you naturally get a $1$ in that position. We want to make sure that the subset adding up to $11\ldots 11$ actually corresponds to a perfect 3-D matching.