[Math] Reduce Independent Set to Path Selection problem

algorithmsgraph theorynp-complete

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

  • Since we want to convert a "don't share any edges" problem to a "don't share any node" problem, it makes sense to give $D$ a node for every edge of $G$.
  • In the independent set problem, the vertices can't share edges; in the path selection problem, the paths can't share nodes. So for every vertex $v_i$ of $G$, we should have a path $P_i$ in $D$.
  • Once we've done that, the edge set of $D$ can just be the union of these paths.

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

  1. Define the node set of $D$ to consist of source nodes $s_1, s_2, \dots, s_n$, sink nodes $t_1, t_2, \dots, t_n$, and intermediate nodes $u_1, u_2, \dots, u_m$.
  2. Then, for every vertex $v_i$ of $G$ incident to edges $e_{j_1}, e_{j_2}, \dots, e_{j_{d(i)}}$, create the path $P_i$ with edges $$s_i \to e_{j_1} \to e_{j_2} \to \dots \to e_{j_{d(i)}} \to t_i$$ (and also add the edges used to the edge set of $D$).

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

Related Question