\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{epsfig}
\usepackage{latexsym}
\begin{document}
\begin{center}
\bf
Algorithms\\
Computer Science 140 \& Mathematics 168\\
Instructor: B. Thom\\
Fall 2003\\
\rm
Homework 13a\\
Due on 12/12/03 (2pm, my office)\\
\end{center}
\begin{enumerate}
\item \textbf{[25 points] Network Reliability is NPC!}

The Network Reliability Problem (NRP) is a famous problem arising in
the area of network design.  First, a few definitions.  We will
represent a network as an undirected graph with $n$ vertices 
$v_{1}, \dots, v_{n}$.  We say that two paths in the network are 
\emph{disjoint} if they have no vertices in common except for the
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 this definition, we're assuming that each pair of vertices considered
is unique, i.e. $\forall \ v_i,v_j, i \neq j$. In other words,
there are no disjoint path between vertex $i$ and itself (the
number of disjoint paths is 0).
In the interest of reliability, it is desirable to have multiple 
disjoint paths between pairs of nodes in the network.

The Network Reliability Problem (NRP) is defined as follows:
Given is an undirected graph with $n$ vertices $v_{1}, \dots, v_{n}$,
an $n \times n$ symmetric matrix $R_{ij}$ of positive integers, and
a positive integer $b$.  The question is whether there exists a subset
$S$ containing exactly $b$ edges in $G$ such that for \emph {each 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 are constructed using {\em only}
edges from set $S$?

One could imagine NRP being very useful when designing a specific network
configuration. For example, if you had $n$ nodes you wanted to connect together, 
you could begin by assuming you were going to link each node to every other (i.e.
build a complete graph, \$\$\$!), and then, given some desired minimal
number of disjoint paths between node pairs, ask ``How few physical links
can be used to still achieve a desired disjointness?''

Prove that NRP is NP-complete using a reduction from a problem that we have already 
shown to be NP-complete. 








\end{enumerate}
\end{document}
