Given an undirected graph, G. There exists k distinct paths, labelled as < si - ti >,1 ≤ i ≤ k, where any of two paths do not share nodes.
Reduction from 3-SAT by encoding with Gadget
The construction (reduction from 3SAT) can be formed as following:
Assume we have n literals, and m clauses. First, let k = m + n. With each literal xi,1 ≤ i ≤ n, we have a pair of vertices, si and ti that forms two disjoint path of length m connecting them, where m is the number of clauses. One path is called the original path, and the other is the complement path. For each < si - ti >-path, we can go either path, which exactly corresponds to setting xi to true or false respectively. (Going through original path, means xi ≡ T; going through the complement path means xi ≡ T ⇐⇒ xi ≡ F.)
For each clause Cj = xi ∨ xj ∨ xk,1 ≤ j ≤ m. We create another pair of vertices sn+j,tn+j. We add an edge from sn+j to a node on the complement path of xi, if the ith literal is xi, and an edge from this node back to tn+j. Logically, if xi is true, then (si,ti)-path would take the original path, leaving the complement path free for < sn+j - tn+j >-path. Similarly, if the ith literal is xi, we add an edge from sn+j to a node on the original path of xi, and an edge from this node back to tn+j. Logically, if xi is false, then < si - ti >-path would take the complement path, leaving the original path free for < sn+j - tn+j >-path. Please note that if < sn+j - tn+j >-path has more than one choices (that means more than one literal is true), then we can pick any path to go through.
In the case of two clauses Ca and Cb both using the same literal xi, then we connect sn+a, sn+b to a distinct node on the path of literal xi (Now we are consider they are both on original path or both on complement path). For instance, if xi is true, then the original path for (si,ti) is used, and that enables both the clauses Ca,Cb to be taking the complement path, < sn+a - tn+a >,< sn+b - tn+b >, respectively. Hence, any < si -ti >-path would have at most m intermediate node, if all m clauses contain xi literal.
Obviously this construction can be done in polynomial time, in terms of n variable and m clauses.
Φ is satisfiable ⇒ the graph has node disjoint path of size k
Proof. If we have a satisfying assignment, then we can choose one literal in each claus to be true. If the literal is true, then the corresponding (si,ti)-path will take the original path, leaving the complement path free for (sn+j,tn+j)-path (for this clause). In contrast, if the literal is false, then the corresponding (si,ti)-path will take the complement path, leaving the original path free for (sn+j,tn+j)-path (for this clause). Thus, the total number of disjoint path in graph is n + m = k. Thus, satisfied the condition of Node-Disjoint Path Problem. __
The graph has node disjoint path of size k ⇒ Φ is satisfiable.
Proof. If the graph has a k node-disjoint-path, we distinguish the literal path (xi,ti), and the clause path (xn+j,tn+j). To get the satisfying assignment, we declare that each literal in the graph is true, then the each clause will have at least one free path (either original or complement). Thus, the assignment is also satisfied. __