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

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.

• – D.W.
Mar 13, 2023 at 0:52

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