Question

In the NODE-DISJOINT PATHS problem, the input is an undirected graph in which some vertices have been specially marked: a certain number of “sources” ${\mathit{s}}_{\mathbf{1}}\mathbf{,}{\mathit{s}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathit{s}}_{\mathbf{k}}$ and an equal number of “destinations” ${\mathbf{t}}_{\mathbf{1}}\mathbf{,}{\mathbf{t}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathbf{t}}_{\mathbf{k}}$. The goal is to find $\mathbf{k}$ node-disjoint paths (that is, paths which have no nodes in common) where the $\mathbf{i}$th path goes from ${\mathbf{s}}_{\mathbf{i}}$ to ${\mathbf{t}}_{\mathbf{i}}$. Show that this problem is NP-complete.Here is a sequence of progressively stronger hints.

1. Reduce from $\mathbf{3}\mathbf{SAT}$ .
2. For a $\mathbf{3}\mathbf{SAT}$ formula with m clauses and n variables, use $\mathbf{\text{k=m+n}}$ sources and destinations. Introduce one source/destination pair $\left(s_x,t_x\right)$for each variable $\mathbf{x}$ , and one source/destination pair $\left(s_c,t_c\right)$ for each clause $\mathbf{c}$ .
3. For each $\mathbf{3}\mathbf{SAT}$ clause, introducenew intermediate vertices, one for each literal occurring in that clause and one for its complement.

Notice that if the path from ${\mathit{s}}_{\mathbf{c}}$ to ${\mathbf{t}}_{\mathbf{c}}$ goes through some intermediate vertex representing, say, an occurrence of variable $\mathbf{x}$, then no other path can go through that vertex. What vertex would you like the other path to be forced to go through instead?

Short answer

The given problem is NP-Complete.

Step-by-step solution

Explain 3SAT problem.

3SAT problem is the satisfiability problem, that finds the fastest algorithm that shows the given Boolean formula is satisfiable. The problem is satisfiable is the formula results 1 .

Show that the given problem is NP-complete

As given, for any clause $\mathit{c}\mathbf{=}\left(l_1\vee l_2\vee l_3\right)$, set ${\mathbf{s}}_{\mathbf{c}}$ to and to respectively. For each variable , is concatenated with all the to , forms the path. All the concatenates to forms another new path.

From the two paths , one must be chosen, that ensures the consistency of variables. If any clause chooses the vertex , then no other clause is allowed to choose the same vertex.

Consider the following example, Consider that the CNF is to be verified as a satisfiable problem. Let , be the NODE-DISJOINT PATH problem as follows:

Therefore, the given problem is NP-complete has been shown by the above example.