\documentclass[12pt]{article}

\usepackage{fullpage}
\usepackage{graphics,epsfig}

\begin{document}
\begin{center}
\bf
Algorithms, Section 2 \\
Spring 2003\\
\rm
Homework 13a \\
Due Thursday, May 1 \\
\end{center}


\begin{enumerate}

\item \textbf{[10 Points] A Misleading News Story.} The article attached to this homework set
appeared in the New York Times in 1979.  The article is about the discovery of a polynomial
time algorithm for the linear programming problem, discovered by the Russian mathematician
Leonid Khachiyan.   At least one sentence in this article is \emph{not known to be true}.
Indicate each such sentence and explain why it is not known to be true.

\item \textbf{[25 Points] Network Reliability is NP-Complete!}
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.
(In this definition, we're assuming that each pair of vertices considered
is unique, i.e. $\forall \ v_i,v_j, i \neq j$.)
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.

The Network Reliability Problem (NRP) is now 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 of $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 use only edges in $S$? 

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}

