I'm a bit confused about some proof that PATH-SELECTION-PROBLEM is NP-complete (Problem 9, chapter 8 in "Algorithm Design" by Tardos and Kleinberg) that I found in some solution manual here:
The PATH-SELECTION PROBLEM is defined as follows: for a given directed graph and a set of paths we ask if it is possible to select at least $k$ paths so that no pair of paths share any node.
The solution uses polynomial reduction from 3D-MATCHING problem defined as: for distinct $n$-sets $X, Y, Z$ and a set of triples $T$ $\subset$$X \times Y \times Z$ we ask if there is an $n$-subset of $T$ that covers $X \cup Y \cup Z$.
For a given arbitrary instance of 3D-MATCHING, the proposed reduction constructs a directed graph $G=(V, E)$ such that $ V := X \cup Y \cup Z$ and for each triple $\langle x, y, z \rangle $ from $T$ it adds edges $\langle x, y \rangle, \langle y, z \rangle $ to $E$ which define set of paths $\mathcal{P}$. It then claims that there are $n$ legal paths in $G$ iff there exists $n$-subset of distinct triples from $T$ (which is equivalent to saying that it covers sum of $X, Y, Z$).
My confusion is that adding edges as above produces too much paths that yield a solution to PATH-SELECTION having no correspondence in 3D-MATCHING. Let's consider $n=2$, $T= \{ \langle x_{1}, y_{1}, z_{2}, \rangle, \langle x_{2}, y_{1}, z_{1}, \rangle, \langle x_{2}, y_{2}, z_{2}, \rangle \}$. There is no solution for 3D-MATCHING here but in reduction described above we have paths $\langle x_{1}, y_{1}, z_{1},\rangle $ and $\langle x_{2}, y_{2}, z_{2},\rangle $.
EDIT: I think I missed one point: over all paths $\mathcal{P}$ the solution defines a subset $\mathcal{P'} \subset \mathcal{P}$ of the paths that strictly correspond to the triples and then we are only allowed to search for a solution in $\mathcal{P'}$. But this is still odd as it reformulates the PATH-PROBLEM adding up additional constraint ...
