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.


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.