Survivable Network Design is the following problem: We are given two n × n matrices: a cost matrix dij and a (symmetric) connectivity requirement matrix rij. We are also given a budget b. We want to find a undirected graph G = ({1, ..., n}, E) such that the total cost of all edges (i.e. ????(i,j)∈E dij) is at most b and there are exactly rij edge-disjoint paths between any two distinct vertices i and j, or if no such G exists, output "None". (A set of paths is edge-disjoint if no edge appears in more than one of them)

Show that Survivable Network Design is NP-Complete. (Hint: Reduce from a NP-Hard problem in Section 8 of the textbook. )

 

In order to show that Survivable Network Design is NP-Complete, then it is necessary to show that it is present in NP first. Optimal solution is arrived when a question indicated with a yes or no answer problem. The target is to find the minimal cost of edges that satisfies the pairwise connectivity requirements. Since there is no pairwise connectivity, thus the optimal solution arrives to no edge during the travel.

Step-by-step explanation

Explanation:

In Survivable Network Design problem (SNDP), it is given that:

G(V,E) is a undirected graph 

R(i, j) is the connectivity requirement for each pair i,j of the vertices.

(i,j)∈ E dij

Dij is a symmetric ( that means travelling from one place to another)

Undirected graph G= (V, E)

n= IVI

D= dij which can be written as:

Dij=0 if i=j

Dij=1 if {vi,vj} ∈ E

Dij=2 otherwise

Assume:  Dij=0 and Dij = Rij, so that matrix D is symmetric and has zero diagonal. Since the problem is stated with budget B, because of which it now has a yes or no answer, it arrives at a minimal solution. Budget B =n.

By travelling between any two distinct vertices posses the total cost of all edges equals to n plus the number of pairs {vi,vj} , such that i?=j , thereby proving {vi,vj} is not an edge of G. Thus the vertex connectivity version the paths are required to be vertex-disjoint.

Result : No such G exists, output "None".