Show that the network reliability problem is NP-complete

Question

I am having trouble understanding the proof for why this problem is NP-complete.

"Network reliability problem"

Given an undirected graph $G$, we have a positive integer $T(X,Y)$ associated with every pair of vertices $(X,Y)$. We finally have an upper limit $B$. Can we find a subgraph including $B$ edges where every pair of vertices $(X,Y)$ has (at least) $T(X,Y)$ disjoint paths between $X$ and $Y$?

My lecturer showed that we can reduce the Hamiltonian cycle problem to this problem using the following pseudocode:

HamiltonianCycle(G[V,E]):
 return Reliability(G[V,E], T(X,Y)=2 forall (X,Y), B=|V|)

I do not understand why we set $T(X,Y)=2$.

Could someone help me understand?

Answer 1

Suppose that you have an algorithm for Reliability.

I want to solve Hamiltonian Cycle.

What do I do? I ask: can you find a subgraph consisting of at most $n$ edges such that between every pair of vertices there are 2 disjoint paths?

Given $n$ vertices and $n$ edges, there is only one possible graph that satisfies the criterion: the cycle graph.

Reduction from Ham Cycle to Reliability. Let $B=n$ and $T(X, Y) = 2$ for every pair of vertices $X, Y$.