2
$\begingroup$

I've been stuck on this problem for a while now. Here it is:

The Network Reliability Problem (NRP) is defined as follows: Given an undirected graph with $n$ vertices $v_{1}, \dots, v_{n}$, a positive integer weight on each edge, and a $n \times 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 and for every pair of vertices $v_i$ and $v_j$ there exist at least $R_{ij}$ disjoint paths from $v_{i}$ to $v_{j}$ such that all paths use only edges in $S$.


I tried showing a reduction from Undirected Hamiltonian Cycle as follows, but I'm not quite sure where to go from there. Any help is appreciated!

The decision version of this problem is as follows: Is there a subset $S$ of edges such that the total cost is at most $k$ and for every pair of vertices $v_i$ and $v_j$ there exist at least $R_{ij}$ disjoint paths from $v_{i}$ to $v_{j}$ such that all paths use only edges in $S$?

We will show that NRDP is NP-hard by reduction from UHC. The reduction is as follows: Given an instance of UHC $G = (V,E)$, create an instance of NRDP by having $ n = |V|$ vertices and let $e = 1, e \in E$, else $e = 2$. Then, create an $n \times n$ matrix with the the vertices listed on the axes, and the cells filled in with the edge weight between the corresponding endpoints.

$\endgroup$
  • 2
    $\begingroup$ I see no question here. $\endgroup$ – Raphael Apr 12 '16 at 9:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.