\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{CS7800}{Advanced Algorithms}{Fall 2014}{25 October 2014}{13}

\begin{center}
\Large{\bf Problems of the Week -- 9 and 10}
\end{center}

{\bf 9. Decomposition of flows}

Given a flow network $G$ and a flow $f$ in $G$, show that it can be
decomposed into at most $m$ path flows, where $m$ is the number of
edges in $G$.  Give a polynomial-time algorithm for this task.  (A path
flow is a flow in the network in which all the positive flow occurs
along a simple path from source to sink, and each edge in the path
carries the same amount of flow.)

{\bf 10. Finding a minimum cut with minimum number of edges}

Given a flow network $G$, suppose you are interested in finding, among
all minimum cuts in $G$, one that contains the fewest number of edges
in $G$.  Show how to create a new flow network $G'$ in which any
minimum cut is a minimum cut in $G$ with the minimum number of edges.

\end{document}