Reduction: 3D Matching → ZOE

ZOE: given a m×nm \times n matrix AA with 0−10-1 entries, and we must find a 0−10-1 vector x=[x1x2⋯xn]⊤x = \begin{bmatrix} x_1 &x_2 &\cdots &x_n \end{bmatrix}^{\top} such that the mm equations

Ax⃗=1⃗A\vec{x} = \vec{1}

are satisfied.

To express 3D matching to ZOE(m boys, m girls, m pets, and n boy-girl-pet triples), we have 0−10-1 variables x1,…,xnx_1, \dots, x_n one per triple, meaning if the triple is chosen(1 for chosen, 0 for not) for the matching. Suppose for each boy/girl/pet the triples containing him/her/it are j1,j2,…,jkj_1, j_2, \dots, j_k, then the appropriate equation

xj1+xj2+⋯+xjk=1x_{j_1} + x_{j_2} + \cdots + x_{j_k} = 1

Which states that exactly one of these triples must be included in the matching.