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?

Step by step solution

01

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 .

02

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.

Unlock Step-by-Step Solutions & Ace Your Exams!

• Full Textbook Solutions

  Get detailed explanations and key concepts

• Unlimited Al creation

  Al flashcards, explanations, exams and more...

• Ads-free access

  To over 500 millions flashcards

• Money-back guarantee

  We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!