\documentclass[12pt]{article}

\usepackage{graphicx}
\usepackage{amsmath,amssymb,url}
\usepackage{bbm}

\newfont{\bssdoz}{cmssbx10 scaled 1200}
\newfont{\bssten}{cmssbx10}


\oddsidemargin  0in \evensidemargin 0in \topmargin -0.5in
\headheight 0.25in \headsep 0.25in
\textwidth   6.5in \textheight 9in %\marginparsep 0pt \marginparwidth 0pt
\parskip 1.5ex  \parindent 0ex \footskip 20pt

\begin{document}
\parindent 0ex
\thispagestyle{empty} \vspace*{-0.75in}
{\bssdoz CME 305: Discrete Mathematics and Algorithms}
{\\ \bssten Instructor: Professor Amin Saberi (saberi@stanford.edu) }
{\\ \bssten HW\#2 --  Due Tuesday 02/14/12}
\vspace{5pt}

\begin{enumerate}

\item Exhibit a graph $G=(V,E)$ where there are an exponential (in $|V|=n$, the number of nodes) number of minimum cuts between a
particular pair of vertices. Do this by constructing a family of graphs parameterized on $n$ and give a pair of vertices $s,t$ such
that there are exponentially many minimum cuts between $s$ and $t$.

\item 
Let $G=(V,E)$ be a graph and $w:E\rightarrow R^{+}$ be an assignment of nonnegative weights to its edges. For $u,v \in V$ let $f(u,v)$ denote the weight of a minimum $u-v$ cut in $G$.
\begin{enumerate}
\item Let $u,v,w \in V$, and suppose $f(u,v) \leq f(u,w) \leq f(v,w)$. Show that $f(u, v) = f(u, w)$, i.e., the two smaller numbers are equal.
\item Show that among the ${n \choose 2}$ values $f(u, v)$, for all pairs $u, v \in V$ , there are
at most $n-1$ distinct values. 
\item Show that for $u,v,w_1,\ldots,w_r \in V$
$$f(u, v) \geq \min(f(u, w_1), f(w_1, w_2), . . . , f(w_r, v))$$
\item 
Let $T$ be a tree on vertex set $V$ with weight function $w'$ on its edges. We will say that $T$ is a flow equivalent tree if it satisfies the first of the two Gomory-Hu conditions. i.e., for each pair of vertices $u, v \in V$, the weight of a minimum $u-v$ cut in $G$ is the same as that in $T$. Let $K$ be the complete graph on $V$. Define the weight of each edge $(u, v)$ in $K$ to be $f(u, v)$. Show that any maximum weight spanning tree in $K$ is a flow equivalent tree for $G$. \\
\textbf{Hint:}	For $u,v \in V$, let $u,w_1,...,w_r,v$ be the unique path from $u$ to $v$ in $T$. Use the previous part and the fact that since $T$ is a maximum weight spanning tree, $f(u, v) \leq \min(f(u, w_1), \ldots, f(w_r, v))$.
\end{enumerate}

\item Let $V$ be a finite set.  A function $f\colon 2^V \to R$ is submodular iff for any $A,B \subseteq V$, we have
$$  f(A \cap B) + f(A \cup B) \leq f(A)+f(B)$$
Now consider a graph with nodes $V$. For any set of vertices $S\subseteq V$ let $f(S)$ denote the number of edges $e=(u,v)$ such that $u\in S$ and $v\in V-S$. Prove that $f$ is submodular.

%It is worth noting all submodular functions can be minimized in polynomial time, and that many discrete optimization problems can be recast as submodular optimization, with the Minimum Cut problem being a famous example.

\item
Prove that the cover time of any connected undirected graph $G$ satisfies $C(G) \leq 2m (n-1)$.
{\bf Hint:} Try to bound the cover time of the spanning tree of $G$ first.

\item
Consider a model of a nonbipartite \textit{undirected} graph in
which two particles (starting at arbitrary positions) follow a random walk i.e. with each time step
both particles uniform randomly move to one of the neighbors.
\begin{enumerate}
\item Prove that
the expected time until they collide is polynomial in the graph size. A collision is when
both particles are on the same node at the same time step.

\item Prove that cover time of certain strongly-connected \textit{directed} graphs
cannot be bounded by any polynomial in the number of vertices. Do so by exhibiting
a strongly connected non-bipartite graph (not a multi-graph) for which the cover time
is super-polynomial.
\end{enumerate}


\item A \emph{cycle cover} $C$ of a directed graph $G(V,E)$ is a collection of 
vertex-disjoint directed cycles so that each vertex in $V$ belongs to some cycle 
in $C$. Give a polynomial time algorithm to compute a cycle cover of a given
directed graph. If there is no cycle cover of $G$, your algorithm must correctly report that there is no cycle cover.

\item {\bf(Kleinberg Tardos 7.27)}
Some of your friends with jobs out West decide they really need some extra time 
each day to sit in front of their laptops, and the morning commute from Woodside 
to Palo Alto seems like the only option.  So they decide to carpool to work.
Unfortunately, they all hate to drive, so they want to make sure that any carpool 
arrangement they agree upon is fair and doesn't overload any individual with too 
much driving.  Some sort of simple round-robin scheme is out, because none of them 
goes to work every day, and so the subset of them in the car varies from day to day.

Here's one way to define \emph{fairness}.  Let the people be labeled 
$S=\{p_1,\ldots,p_k\}$.  
We say that the \emph{total driving obligation} of $p_j$ over a set of days is 
the expected number of times that $p_j$ would have driven, had a driver been 
chosen uniformly at random from among the people going to work each day.  
More concretely, suppose the carpool plan lasts for $d$ days, and on the $i^{th}$ 
day a subset $S_i\subseteq S$ of the people go to work. Then the above definition 
of the total driving obligation $\Delta_j$ for $p_j$ can be written as 
$\Delta_k = \sum_{i: p_j \in S_i} \frac 1 {|S_i|}$.  
Ideally, we'd like to require that $p_j$ drives at most $\Delta_j$ times; 
unfortunately, $\Delta_j$ may not be an integer.

So let's say that a \emph{driving schedule} is a choice of a driver for each day ---
that is, a sequence $p_{i_1},p_{i_2},\ldots,p_{i_d}$ with $p_{i_t} \in S_t$ ---
and that a \emph{fair driving schedule} is one in which each $p_j$ is chosen as 
the driver on at most $\lceil \Delta_j \rceil$ days.

\begin{enumerate}
 \item Prove that for any sequence of sets $S_1,\ldots,S_d$, there exists a fair 
 driving schedule.
 \item Give an algorithm to compute a fair driving schedule with running time 
 polynomial in $k$ and $d$.
\end{enumerate}


\end{enumerate}

\end{document}