$7.$ Optional extra$-$credit question: Network reliability.

The Republic of Alvonia owns the internal internet infrastructure for the country and leases out

connections to Internet Service Providers $($ISPs$).$ We represent that network as an undirected

graph. Assume that each edge in the graph has a positive integer rental cost associated with

it$.$ An ISP is confronted with the problem of spending the minimum amount of money on link

rental so that it can provide adequately reliable service to its customers.

Here is how we quantify reliability: We say that two paths in the network are disjoint if they

have no vertices in common, except for possibly their endpoints. For example, there can be

two disjoint paths from vertex v$\_(42)$ to v$\_(100),$ but v$\_(42)$ and v$\_(100)$ can be the only vertices that these

paths have in common $($since these vertices are the endpoints of the paths$).$ In the interest of

reliability, it is desirable to have multiple disjoint paths between pairs of nodes in the network.

Some ISPs provide more reliability than others, but they may charge their clients more.

The Network Reliability Optimization Problem $($NROP$)$ is now defined as follows. An instance

is an undirected graph with n vertices v$\_(1),$dots,v$\_($n$),$ a non$-$negative integer weight on each edge,

and an n$-$by$-$ n symmetric matrix R$\_($ij$).$ The objective is to find a subset S of the edges such

that the total cost of the edges in S is minimized, with the requirement that for every pair of

vertices v$\_($i$)$ and v$\_($j$),$ there are at least R$\_($ij$)$ disjoint paths from v$\_($i$)$ to v$\_($j$)$ such that all paths use only

edges in S$.$

You've been hired as a summer intern to develop an efficient algorithm for solving NROP. After

working on an algorithm for awhile, your team conjectures that the problem is NP$-$hard. Here

is your task:

Define the decision version of this problem, which we will call NRDP;

Prove that NRDP is NP$-$hard via a reduction from an NP$-$hard problem from lecture.