Can anybody explain how the exact reduction of the Independent Set to Path Selection problem works?
I understand that if $G = (V,E)$ is a graph, where $(G,k)$ is an instance of the Independent set problem then we can map the edges of $G$ to nodes in a new graph, $G'$, where now we will prove that there are $k$ node disjoint paths. But exactly how to come up with the reduction of $G$ to $G'$ is what I am wondering.
Any explanation would be very useful.
Thanks.
Best Answer
The independent set problem asks: given a graph $G$ and an integer $k$, can we choose $k$ of the vertices of $G$ with no edges between them?
The path selection problem asks: given a digraph $D$, a list of directed paths $P_1, \dots, P_c$ in the digraph, and an integer $k$, can we choose $k$ of the paths that do not share any nodes?
To reduce the former to the latter, we must use $G$ to build a digraph $D$ and a set of paths $P_1, \dots, P_c.$
The task is not actually very constrained. Here's one way to accomplish it. Let $e_1, e_2, \dots, e_m$ be the edges of $G$ in some fixed order, and $v_1, v_2, \dots, v_n$ be the vertices of $G$.
It should be clear that a set of $k$ paths shares no nodes if and only if the corresponding vertices of $G$ have no edges between them.
(The sources and sinks are just there to make sure isolated vertices of $G$ still actually have a path in $D$ to be represented by.)