\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: Reza Zadeh (rezab@stanford.edu) }
{\\ \bssten HW\#3 --  Due at the beginning of class Thursday 02/25/16}
\vspace{5pt}

\begin{enumerate}

\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. Prove that
the expected time until they collide is $O(n^6)$. A collision is when
both particles are on the same node at the same time step.

\item Let $A$ be a $n \times n$ matrix, $B$ a $n \times n$ matrix and $C$ 
a $n \times n$ matrix. We want to design an algorithm that checks whether 
$AB = C$ without calculating the product $AB$. Provide a randomized algorithm
that accomplishes this in $O(n^2)$ time with high probability.

\item
Given a connected, undirected graph $G = (V,E)$ and a set of terminals
$S=\{s_1, s_2,\ldots,s_k\} \subseteq V$, a multiway cut is a set of edges whose 
removal disconnects the terminals from each other. The multiway cut problem asks for the minimum weight such set.
The problem of finding a minimum weight multiway cut is NP-hard for any fixed $k \geq 3$.
Observe that the case $k = 2$ is precisely the minimum $s-t$ cut problem.

Define an \textit{isolating cut} for $s_i$ to be a set of edges whose removal disconnects $s_i$ from the rest of the terminals. Consider the following algorithm
\begin{itemize}
	\item For each $i = 1,\ldots, k$, compute a minimum weight isolating cut for $s_i$, say $C_i$.
	\item Discard the heaviest of these cuts, and output the union of the rest, say C.
\end{itemize}

Each computation in Step 1 can be accomplished by identifying the $terminals$ in $S - \{s_i\}$ into a single node, and finding a minimum cut separating this node from $s_i$; this takes one max-flow computation. Clearly, removing $C$ from the graph disconnects every pair of terminals, and so is a multiway cut.

\begin{enumerate}
\item Prove that this algorithm achieves a $2-2/k$ approximation.
\item Prove that this analysis is tight by providing an example graph where the approximation bound is exactly achieved.
\end{enumerate}

\item Consider variants on the metric TSP problem in which the object is to find a simple path containing all the vertices of the graph. Three different problems arise, depending on the number (0, 1, or 2) of endpoints of the path that are specified. If zero or one endpoints are specified, obtain a 3/2 factor algorithm. 

\textbf{Hint.} Consider modifying Christofides algorithm for metric TSP.

\item Recall the \emph{minimum vertex cover} problem: given a graph
$G(V,E)$ find a subset $S^* \subseteq V$ with minimum cardinality such
that every edge in $E$ has at least one endpoint in $S^*$.
Consider the following greedy algorithm. Find the highest degree
vertex, add it to the vertex the $S$ and remove it along with all
incident edges. Repeat iteratively. Prove that this algorithm has an
unbounded approximation factor i.e.  for any $c$ there exists an input
graph $G$ such that $|S|$ $\geq c$ OPT.


\item A dominating set of a graph is a subset of vertices such that every node in the graph is either in the set or adjacent to a member of the set. The DOMINATING-SET problem is as follows: given a graph $G$ and a number $k$, determine if $G$ contains a dominating set of size $k$ or less. 
\begin{enumerate}
\item Show the DOMINATING-SET problem is NP-complete. 
\item Obtain a ln$(n)$-approximation to the DOMINATING-SET problem. 
\end{enumerate}

\item 
An oriented incidence matrix $B$ of a directed graph $G(V,E)$ is a matrix with
$n = |V|$ rows and $m = |E|$ columns with entry $B_{ve}$ equal to $1$ if edge $e$ 
enters vertex $v$ and $-1$ if it leaves vertex $v$. Let $M = BB^T$. 

\begin{enumerate}
\item Prove that $rank(M) = n - w$ where $w$ is the number of connected components of $G$. 

\item  Show that for 
any $i \in \{1,\dots,n\}$,
\[\det M_{ii} = \sum_N (\det N)^2,\]
where $M_{ii} = M\backslash \{i^{th}$ row and column\}, and $N$ runs over
all $(n - 1) \times (n - 1)$ submatrices of $B\backslash\{i^{th}$ row\}.
Note that each submatrix $N$ corresponds to a choice of $n-1$ edges of $G$.

\item Show that 
\[\det N = 
\left\{ 
\begin{array}{rl}
\pm 1 & \mbox{if edges form a tree} \\
0 & \mbox{otherwise}
\end{array}
\right.
\] 
This implies that $t(G) = \det M_{ii}$, where $t(G)$ is the number of spanning 
trees of $G$. In this definition of a tree, we treat a directed edge as an 
undirected one.

\item Show that for the complete graph on $n$ vertices $K_n$, 
\[\det M_{ii} = n^{n-2}.\]

\end{enumerate}

\item Given a sequence $p_i$ of stock prices on $n$ days, we need to find the best pair of days to buy and sell. i.e. find $i$ and
$j$ that maximizes $p_{j}-p_{i}$ subject to $j \geq i$. Give an $O(n)$ dynamic programming solution.

\item Let $G$ be a graph with minimum degree 3. Show $G$ contains a cycle of even length.


\end{enumerate}

\end{document}