3
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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$.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.