\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$. \textbf{Solution.} For $n=3$, we simply have a path of length 2 between the two ends $s$ and $t$. For $n>3$, each new vertex will be connected to $s$ and $t$ (and nothing else) creating an additional path of length $2$ between $s$ and $t$. For general $n$, to separate $s$ and $t$, we must cut one edge along every edge-disjoint path between them. There are $n-2$ paths between $s$ and $t$, each of length 2. So we have $n-2$ binary choices, giving $2^{n-2}$ different minimum cuts. \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. \textbf{Solution.} Consider the two ends of the smallest edge $u$ and $v$. Let \\$c = \min(f(u, w), f(w, v))$. We can route route $c$ units of flow from $u$ to $w$ and then from $w$ to $v$. This means $f(u,v) \geq c = \min(f(u, w), f(w, v)) = f(u, w)$, which is only possible if $f(u, v) = f(u, w)$. \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. \textbf{Solution.} We prove this by induction on the number of nodes. The result is clearly true for a graph with 3 nodes from part a. Assume the result for all graphs $G'$ of size $n$, and consider a graph $G$ with $n+1$ nodes. There will be a largest edge, pick one of its two vertices, call it $v$. Order the edges incident upon $v$ in decreasing order: $f_1, f_2, \ldots, f_{n}$. So $f_1$ is the largest edge in $G$. Note that the $f_i$ are sides of triangles of all whom have one edge in the smaller graph $G'$, where there are only $n-2$ distinct edges by induction hypothesis. We argue that other than $f_1$, all the other $f_i$ are equal to some edge in $G'$, thus the number of distinct edges in $G$ can only one larger, with the contribution coming from $f_1$. This is true because of the decreasing ordering on the $f_i's$ and the triangle property from part a, enforcing each $f_2,\ldots,f_n$ be equal to some edge in $G'$. Thus the addition of $v$ can only add one new distinct edge weight: $f_1$, making for at most $n-1$ distinct weights. \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))$$ \textbf{Solution.} This holds by a similar argument to part a, i.e. we can route flow from $u$ to $w_1$ to $w_2$ to $\ldots$ to $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))$. \textbf{Solution.} The minimum $u-v$ cut between any two nodes in a tree is the minimum weight edge on the unique path between $s$ and $t$. It remains to show the MST has appropriate weights. For any $u,v$, Kruskal's algorithm for minimum spanning trees gives $$f(u, v) \leq \min(f(u, w_1), \ldots, f(w_r, v))$$ and from the previous part we have $$f(u, v) \geq \min(f(u, w_1), \ldots, f(w_r, v))$$ thus $f(u, v) = \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. \begin{center} \includegraphics[width=70mm]{sub.png} \end{center} \textbf{Solution.} To see this, notice that $f(A) + f(B) = a + b + 2c + d + e + 2f$, for any arbitrary $A$ and $B$, and $a, b, c, d, e, f$ are as shown in the figure. Here, $a$ (for example) represents the total capacity of edges with one endpoint in $A$ and the other in $V - (A \cup B)$. Also notice that $f(A \cap B) + f(A \cup B) = a+b+ 2c+d+e$, and since all values are positive, we see that $f(A) +f(B) \geq f(A \cap B) + f(A \cup B)$ , satisfying the definition. Thanks to \footnote{\url{http://www.cs.illinois.edu/class/sp10/cs598csc/Lectures/Lecture6.pdf}} for the figure. 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. \textbf{Solution.} Let $x$ be the vertex such that $C_x$ is maximum (recall that $C(G) = \max_x C_x$) and let $T$ be a spanning tree of $G$ such that $x$ is a leaf. Consider a tour $U= x_1, x_2, \dots, x_{2n}$ with $x_1 = x_{2n} = x$ of $T$ such that each edge is travered exactly twice. To see why one exists transform $T$ into a directed graph by introducing directed edges $(x,y)$ and $(y,x)$ in place of edge $\{x,y\} \in E(T)$ in the tree and note that this graph is Eulerian. Consider the following process on $G$. Start a random walk at vertex $x$ which is allowed to mark vertices in the order specified by the tour. This process terminates at vertex $x$ at which point each vertex has been visited at least twice. Let the expected number of steps this process takes be denoted by $W$. Note that $C(G) \leq W$ and we can compute $W$ as follows. \[ W = \sum_{k\,=\,1}^{2n-1} H_{x_kx_{k+1}} = \sum_{\{x,y\} \in E(T)} C_{xy} = 2m \sum_{\{x,y\} \in E(T)} R_{xy} \] Since the resistance on each edge $\{x,y\}$ is unit we must have that the effective resistance $R_{xy} \leq 1$ whenever $x$ and $y$ are adjacent. Since the number of edges in $T$ is $n-1$ we have that $C(G) \leq W \leq 2m (n-1)$ as desired. \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. \textbf{Solution.} Suppose our graph is $G = (V, E)$. Now consider the graph $G' = (V \times V, E')$, where $E' := \{ ((a,b),(c,d)) | (a,c),(b,d) \in E \}$. First we show that if $G$ is connected and non-bipartite, then so is $G'$. If $G$ is non-bipartite, then it has an odd cycle $v_1, v_2, ..., v_k$. But then so has $G'$ with $(v_1,v_1), (v_2,v_2), \ldots, (v_k, v_k)$, and is therefore also non-bipartite. As for connectivity, consider two vertices $(a, b)$ and $(c, d)$ in $G'$. There are paths in $G$ from $a$ to $c$, and from $b$ to $d$. Moreover, these paths can be made to have the same length (although they are not necessarily simple then). This can done as follows: \begin{itemize} \item if the two path lengths have different parity (i.e. one has even length, the other has odd length), then do the following: consider a path from $a$ to $c$ that goes through $v_1$ (since $G$ is connected, this - not necessarily simple - path exists). If this pathÕs length does not have the same parity as the length of the path from $b$ to $d$, then add the odd cycle $v_1, v_2, \ldots, v_k, v_1$ to the path from $a$ to $c$. Since the path visits $v_1$ this cycle can just be inserted. After this, both path lengths have the same parity. \item if they still have different lengths, make the shorter of the two paths longer by adding 2-cycles at its end. E.g., if the path from $a$ to $c$ is shorter, and $x$ is some neighbor of $c$, then add a sequence $c,x,c,x,\ldots,x,c$ to the end of the path to make it have the same length as the other path. \end{itemize} Given two paths of the same length from $a$ to $c$, and $b$ to $d$, we can easily construct a path in $G'$ from $(a, b)$ to $(c, d)$, by following the path from $a$ to $c$ in the first component, and the path from $b$ to $d$ in the second component. So $G'$ is connected. Now back to the problem of parallel Markov processes. A random walk $G'$ has the same behavior as two independent random walks on the graph $G$. This is because we have $deg_G((u, v)) = deg_G(u) deg_G(v)$, so the probability to go from a node $(a, b)$ to a node $(c, d)$ in $G'$ is the same as independently going from $a$ to $c$, and from $b$ to $d$ in two random walks on $G$. In the previous question we proved a cubic cover time for any undirected graph, so in particular $G'$ has a cover time of $O(n^6)$. This implies that all nodes of the form $(a,a)$ in $G'$ are reached in polynomial time, which means that the two random walks meet in polynomial time. \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. \textbf{Solution.} Consider the directed graph on nodes $1, \ldots, n$ which has directed edges $(i, i + 1)$ and $(i, 1)$ for all $i$. A sequence of transitions that gets from vertex $1$ to vertex $n$ must have an uninterrupted sequence of $n$ transitions along edges $(i, i + 1)$. The probability of such a subsequence occurring in a given sequence of $n$ tries is $2^{-n}$, so in a sequence of length (say) $1.9n$, such a subsequence is exponentially unlikely to occur. Thus, with high probability it takes exponential time to cover the graph. \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. \textbf{Solution.} Let A = V and B = V and connect with directed edges from A to B if edge is on original graph. If there exists a perfect matching, in which the vertex $v_i$ in $A$ is matched to $v_{\pi(i)}$ in $B$. Here $\{\pi(1), \ldots, \pi(n)\}$ is a permutation of $\{1, 2, \ldots, n\}$. Then we see that the edges $\{(v_i, v_{\pi(i)}): i = 1, 2, \ldots, n\}$ forms a circle cover. Thus determining whether there exists a circle cover is equivalent to deciding whether there exists a perfect matching. We can use the network flow to solve this problem effectively. \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} \textbf{Solution.} We convert the problem into a network flow problem. First we construct a graph as follows. We denote the vertex $p_i$ as the $i$-th driver. Moreover we denote the vertex $q_j$ as the $j$-th day. If $p_i$ can drive on the $j$-th day, we simply draw a directed edge from $p_i$ to $q_j$ of capacity 1. Finally we draw a source $s$ which connects each $p_i$ with capacity $\lceil\Delta_i\rceil$ and a sink which connects each $q_j$ with capacity $1$. It is easy to find that computing a fair driving schedule is equivalent to computing the maximum flow problem. The only thing we need to do is to prove that the value of the maximum flow is $d$. First of all, it is obvious that for any flow $f$, $|f|\leq d$. Thus if we are able to find a flow $f$ with $|f|=d$, we are done. This is easy to achieve. Consider the following flow. \[ f_{p_iq_j} = \frac{1}{|S_j|},\qquad f_{sp_i} = \sum_{j: p_i\in S_j}\frac{1}{|S_j|}\leq\lceil\Delta_i\rceil,\qquad f_{q_jt} = 1. \] This flow satisfies all the constraints and have value $n$. Thus there exists a fair schedule. For computing it, we simply adopt the Ford algorithm. \end{enumerate} \end{document}