\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}{14 October 2014}{12}

\begin{center}
\Large{\bf Problem Set 4 (due Thursday, October 23)}
\end{center}


{\bf 1. (10 points) The escape problem}

Problem 26-1 of text.

{\bf 2. (7 + 8 = 15 points) Updating the maximum flow}

Problem 26-4 of text.

{\bf 3. (10 + 5 = 15 points) Tight-knit communities in social networks}

Social networks are all the craze these days.  Assuming that
friendship links are symmetric, one can represent a social network
such as Facebook as an undirected unweighted graph $G$.  Identifying
clusters, communities, and other connectivity properties is a hot
topic of research.

Suppose you want to identify a tight-knit community in a social
network $G$.  For a given set $S$ of nodes in $G$, let $n(S)$ denote
the number of edges with both endpoints in $S$.  Define the {\em
  connectedness}\/ of any set $S$ of nodes in $G$ to be $n(S)/|S|$.
Larger the $n(S)$, the more tight-knit $n(S)$ is; dividing by $|S|$
normalizes across sets of different sizes.

\begin{itemize}
\item[{\bf (a)}] Give a polynomial time algorithm that takes a
  rational number $\alpha$ and determines whether there exists a set
  $S$ with connectedness at least $\alpha$.

\item[{\bf (b)}] Use the above algorithm to find a set $S$ of nodes
  with maximum connectedness.
\end{itemize}

{\bf 4. (5 + 2 + 3 = 10 points)} {\bf Pathalogical example for the
  basic augmenting path algorithm}

In the residual network $G_f$ corresponding to a flow $f$, define an
{\em augmenting walk}\/ as a directed walk from source $s$ to sink $t$
that visits any arc at most once (it might visit nodes multiple
times-- in particular, an augmenting walk might visit nodes $s$ and
$t$ multiple times).  Define the {\em residual capacity}\/ of an
augmenting walk to be the residual capacity (i.e., capacity in $G_f$)
of the minimum-capacity edge in the walk.

\begin{itemize}
\item[{\bf (a)}] 
Consider the network shown in Figure~\ref{fig:pow13}(a) with the edges
labeled $a$, $b$, $c$, and $d$; note that one arc capacity is
irrational.  Show that this network contains an infinite sequence of
augmenting walks whose residual capacities sum to the maximum flow
value.  ({\em Hint} : Each augmenting walk of the sequence contains
exactly two arcs from node $s$ to node $t$ with finite residual
capacities.)

\begin{figure}[htb]
\input{Figures/network.tex}
\caption{\small A pathological example for the basic augmenting path algorithm.}
\label{fig:pow13}
\end{figure}

\item[{\bf (b)}] 
Now consider the network shown in Figure~\ref{fig:pow13}(b).  Show
that this network contains an infinite sequence of augmenting walks
whose residual capacities sum to a value different than the maximum
flow value.

\item[{\bf (c)}] 
Next consider the network shown in Figure~\ref{fig:pow13}(c); in
addition to the edges shown, the network contains an infinite capacity
edge connecting each node pair in the set $\{1, 2, 3, 4\}$ as well as
each node pair in the set $\{1', 2', 3', 4'\}$.  Show that each
augmenting walk in the solution of part (b) corresponds to an
augmenting path in Figure~\ref{fig:pow13}(c).  Conclude the basic
augmenting path algorithm, when applied to a maximum flow problem with
irrational capacities, might perform an infinite sequence of
augmentations and the terminal flow value might be different than the
maximum flow value.
\end{itemize}
\end{document}
