4.13.8 K Node Disjoint Path

Definition

Given an undirected graph, G. There exists k distinct paths, labelled as < s_i - t_i >,1 ≤ i ≤ k, where any of two paths do not share nodes.

Polynomial Certifier

• Input: Given an undirected graph, G = (V,E).
• Certificate: k distinct paths, labelled as < s_i - t_i >,1 ≤ i ≤ k.
• Certifier: When traversing a path, we remove nodes from set V. If there exists a node in another path such that the node was already removed. Then, we know that there are two paths that share common nodes, and vice versa.
• Running Time: The summation of traversing k-path. O(n⋅k) if all k paths have every nodes in V.

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 x_i,1 ≤ i ≤ n, we have a pair of vertices, s_i and t_i 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 < s_i - t_i >-path, we can go either path, which exactly corresponds to setting xi to true or false respectively. (Going through original path, means x_i ≡ T; going through the complement path means x_i ≡ T ⇐⇒ x_i ≡ F.)

For each clause C_j = x_i ∨ x_j ∨ x_k,1 ≤ j ≤ m. We create another pair of vertices s_n+j,t_n+j. We add an edge from s_n+j to a node on the complement path of x_i, if the i^th literal is x_i, and an edge from this node back to t_n+j. Logically, if x_i is true, then (s_i,t_i)-path would take the original path, leaving the complement path free for < s_n+j - t_n+j >-path. Similarly, if the i^th literal is x_i, we add an edge from s_n+j to a node on the original path of x_i, and an edge from this node back to t_n+j. Logically, if x_i is false, then < s_i - t_i >-path would take the complement path, leaving the original path free for < s_n+j - t_n+j >-path. Please note that if < s_n+j - t_n+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 C_a and C_b both using the same literal x_i, then we connect s_n+a, s_n+b to a distinct node on the path of literal x_i (Now we are consider they are both on original path or both on complement path). For instance, if x_i is true, then the original path for (s_i,t_i) is used, and that enables both the clauses C_a,C_b to be taking the complement path, < s_n+a - t_n+a >,< s_n+b - t_n+b >, respectively. Hence, any < s_i -t_i >-path would have at most m intermediate node, if all m clauses contain x_i 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

The graph has node disjoint path of size k ⇒ Φ is satisfiable.