\documentclass[12pt]{article}
\newcommand{\Bonus}[1]{\textbf{[#1 Points OPTIONAL Bonus Problem]}}
\newcommand{\Points}[1]{\textbf{[#1 Points]}}
\newcommand{\Name}[1]{\textbf{#1}}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{geometry}

\begin{document}
\begin{center}
	\bf
	Algorithms \\
	Computer Science 140 \& Mathematics 168 \\
	Spring 2009 \\
	\rm
	Homework 11a\\
	Due Thursday, April 9
\end{center}

\begin{itemize}
	\item The famous computational biologist, Professor David Haussler, will be speaking at Harvey Mudd on Wednesday at 4:15 in Galileo Pryne (refreshments at 4 PM).  \textbf{You may attend Professor Haussler's talk in lieu of this assignment.}  If you do so, please send me e-mail at \verb+ran@cs.hmc.edu+ with the subject \verb+Haussler talk+.  In that e-mail please just write a few sentences about what you found most interesting in his talk.  

	\item Please remember that Exam 2 will be distributed in class on Thursday, April 9.  Here are the details:
	\begin{itemize}
		\item The exam will have four questions primarily on advanced data structures and their analysis, graph algorithms, and NP-completeness and related material.
		\item The exam is ``closed-everything'' except that you may use your lecture notes and solution sets that I have distributed.  You may prepare additional notes before the exam in your own hand-writing - these count as your lecture notes.
		\item You may spend as much time as you like on this exam up until the due time:  \textbf{Tuesday, April 14 at 5 PM}.  The exam is to be submitted to Ms.~Joyce Greene in the main CS office at Olin 1258.  \emph{On the HMC honor code, you must submit this exam on time.   In fairness to the your classmates, the due time will be strictly enforced:  late exams will not receive credit.  If you do not submit the exam on time it is expected that you will self-report this on your exam.}
		\item As on the first exam, clarifications may be requested by e-mail until Friday, April 10 at 5 PM.  Answers to clarification questions will be posted on the course
		webpage by Friday, April 10 at 11 PM.
		\item Ran will be away on Monday and Tuesday, April 13 and 14.  \textbf{There will be no class on Tuesday, April 14}.
	\end{itemize}
\end{itemize}

\begin{enumerate}
	\item \Name{Network Reliability is NP-Complete!} \Points{25}
	Millisoft has decided to purchase the entire Internet and rent links to Internet Service Providers (ISPs).  
	
	We represent the internet as an undirected 	graph.   Assume that each edge in the graph has a positive integer \emph{rental cost} associated with it.  The ISPs are confronted with the challenging problem of spending the minimum amount of money on link rental so that they can provide adequately reliable service to their customers.
	
	Here is how we quantify reliability:  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 the interest of reliability, it is desirable to have multiple  disjoint paths between pairs of nodes in the network.   Some ISPs provide more reliability than others and they can charge their clients more accordingly.

The Network Reliability Optimization Problem (NROP) 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 cost associated with each edge.  
The objective is to find a subset $S$ of the edges such that the total cost of the edges in $S$ is minimized \emph{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$.  

Your boss, Gill Bates, has asked you to develop an efficient algorithm for solving NROP optimally for the client ISPs.  
You conjecture that the problem is NP-complete.  State the decision version of this problem, which we will call NRDP, and prove that NRDP is NP-complete using a reduction from a problem that we have already shown to be NP-complete. 



\end{enumerate}
\end{document}