0
$\begingroup$

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:

https://github.com/weimin/CS-180/blob/master/Algorithm%20Design%20(Kleinberg%20Tardos%202005)%20-%20Solutions/Algorithm%20Design%20-%20Kleinberg%20%26%20Tardos%20-%20Solutions/chapter_08/problem%20(8).pdf.

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

$\endgroup$
1
$\begingroup$

The "additional constraint" is part of the problem definition:

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 key is "and a set of paths". The Path-Selection Problem has a set of paths from which you are allowed to chose as part of its input.

Note that the definition is kind of strange, since the fact that a graph is involved seems irrelevant (we could always take the graph to be a clique, which doesn't change the answer). However, if the graph has special structure, then the problem can become tractable (e.g., if the graph is a tree the problem is polynomially solvable).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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