\documentclass[11pt]{article}
\usepackage[margin=1.2in,a4paper]{geometry} % try also "letterpaper" instead of "a4paper"
\usepackage{enumitem} % this package is used to generate the custom chapter prefix "[Chapter number].[Exercise Number]"
\usepackage{amssymb}
\usepackage{amsmath}

%%%%%%%%%% macros %%%%%%%%%%
  \newcommand{\Thm}[1]{Theorem~{#1}}
  \newcommand{\Exe}[1]{Exercise~\ref{#1}}   
%%%%%%%%%% macros %%%%%%%%%%

\begin{document}

%%%%%%%%%% header %%%%%%%%%%
\noindent {\sf\LARGE GENOME-SCALE ALGORITHM DESIGN} \\
\noindent {\sf by Veli M{\" a}kinen, Djamal Belazzougui, Fabio Cunial and Alexandru I. Tomescu}\\
\noindent {\sf Cambridge University Press, 2015}\\
\noindent {\sf www.genome-scale.info}\\
\noindent\makebox[\linewidth]{\rule{\paperwidth}{0.4pt}}
%%%%%%%%%% header %%%%%%%%%%

\section*{Exercises for Chapter 4. Graphs}

\begin{enumerate}[label=4.\arabic*]
\item Find a family of DAGs in which the number of topological orderings is exponential in the number of vertices.
\label{graphs:ex-1}

\item Find a family of DAGs with a number of distinct paths exponential in the number of vertices.
\label{graphs:ex-2}

\item Show that a directed graph $G$ is acyclic (does not contain a directed cycle) if and only if for every subset of vertices $S \subseteq V(G)$, there exists a vertex $v \in S$ such that no out-neighbor of $v$ belongs to $S$. Conclude that a DAG must have at least one sink.

\item Show that a directed graph $G$ is acyclic if and only if it admits a topological ordering (the forward implication is \Thm{4.1}). Conclude that we can check in $O(m)$ time whether a directed graph is acyclic.

\item Let $G$ be a DAG with precisely one source $s$ and one sink $t$. Show that for any $v \in V(G) \setminus \{s,t\}$ there exists a path from $s$ to $v$ and a path from $v$ to $t$.

\item Let $G$ be a DAG with a unique source. Prove that $G$ is connected.

\item \label{exe:eulerian-connectivity} Explain in detail how the connectivity assumption is exploited in the proof of \Thm{4.3}.

\item Show how the procedure in \Thm{4.3} can be implemented in time $O(m)$.
\label{graphs:exe-eulerian}

\item \label{exe:tournament} Consider a directed graph $G$ in which for every pair of vertices $u,v \in V(G)$ exactly one of $(u,v) \in E(G)$ or $(v,u) \in E(G)$ holds (such a graph is called a \emph{tournament}). Show that there exists a path in $G$ passing through all vertices exactly once (such a path is called \emph{Hamiltonian}).

\item Let $G$ be an undirected graph. Show that either $G$ or its complement $\overline{G}$ is connected.

\item Give an algorithm running in time $O(n+m)$ that checks whether an undirected graph $G$ is connected, and if not, lists all of its connected components.

\item A connected undirected graph $G$ is called \emph{2-connected} (or \emph{bi-connected}) if removing any vertex from $G$ (along with its incident edges) results in a connected graph. Give an algorithm running in time $O(m)$ for checking whether a graph is 2-connected.
\label{graphs:ex-2-connected-check}

\item Refine the algorithm from \Exe{graphs:ex-2-connected-check} so that it also outputs the 2-connected components of $G$ (that is, the maximal 2-connected subgraphs of $G$).

\item Given an undirected graph $G$, consider the graph $B(G)$ of 2-connected components of $G$: the vertices of $B(G)$ are the 2-connected components of $G$, and we add an edge between two vertices of $B(G)$ if the corresponding 2-connected components of $G$ have a vertex in common. Show that $B(G)$ is a tree.

\item Consider a directed graph $G$, a vertex $s \in V(G)$, and $c : E(G) \rightarrow \mathbb{Q}$ so that no cycle of $G$ has negative cost. Show that if $G$ has only two 2-connected components $C_1$ and $C_2$, sharing a vertex $v$, such that $s \in V(C_1)$, then we can solve the shortest-path problem on $G$ by solving it independently on $C_1$ and $C_2$, by appropriately initializing the dynamic programming algorithm on $C_2$ at vertex $v$.

\item Consider a DAG $G$, a vertex $s \in V(G)$, a cost function $c : E(G) \rightarrow \mathbb{Q}$, a partition $\mathcal{S} = \{S_1,\dots,S_k\}$ of $V(G)$, and an integer $t \leq k$. Give a dynamic programming algorithm for computing a shortest path from $s$ to any other vertex of $G$ that changes the partite sets of $\mathcal{S}$ at most $t$ times. What is the complexity of your algorithm? What if $G$ is not acyclic?
\label{graphs:exe-partitioned-DAG}

\item Consider a DAG $G$, a partition $\mathcal{S} = \{S_1,\dots,S_k\}$ of $V(G)$, and an integer $t \leq k$. We say that a path $P = u_1,u_2,\dots,u_\ell$ in $G$ is \emph{$t$-restricted} if every maximal subpath of $P$ of vertices from the same set of $\mathcal{S}$ has at least $t$ vertices. (In other words, if $P$ starts using vertices from a set $S_i \in \mathcal{S}$, then it must do so for at least $t$ vertices.) Give a dynamic programming algorithm that is additionally given a vertex $s \in V(G)$ and a cost function $c : E(G) \rightarrow \mathbb{Q}$, and finds a $t$-restricted shortest path from $s$ to any other vertex of $G$. What is the complexity of your algorithm? What if $G$ is not acyclic?

\item Given a directed graph $G = (V,E)$, $n = |V|$, $m = |E|$, and a cost function $c : E \rightarrow \mathbb{Q}$, we say that the \emph{length} of a cycle $C = v_1,v_2,\dots ,v_t,v_{t+1}\!=\!v_1$ in $G$, denoted $l(C)$ is $t$, its \emph{cost}, denoted $c(C)$, is $\sum_{i = 1}^{t}c(v_i,v_{i+1})$, and its \emph{mean cost} is $\mu(C) = c(C)/l(C)$. Denote by $\mu(G)$ the minimum mean cost of a cycle of $G$, namely
\[\mu(G) = \min_{C \text{ cycle of } G}\mu(C).\]

\begin{enumerate}
\item[(\emph{a})] For each $v \in V(G)$, and each $k \in \{0,\dots,n\}$, let $d(v,k)$ be the minimum cost of a path in $G$ with exactly $k$ edges, ending at $v$ (where $d(v,0) = 0$ by convention). Show that the bi-dimensional array $d$ can be computed in time $O(nm)$.

\item[(\emph{b})] Show that
\begin{equation}
\mu(G) = \min_{v \in V} \max_{0 \leq k \leq n-1} \frac{d(v,n) - d(v,k)}{n-k},
\label{eq:ex-minimum-mean-cycle}
\end{equation}
by showing the following facts. Consider first the case $\mu(G) = 0$, and show that

\begin{itemize}
\item for any $v \in V$, there exists a $k \in \{0,\dots,n-1\}$ such that $d(v,n) - d(v,k) \geq 0$, thus, the right-hand side of (\ref{eq:ex-minimum-mean-cycle}) is greater than or equal to 0;
\item each cycle of $G$ has non-negative cost: if $C$ is a cycle of $G$, then there exists a vertex $v$ on $C$ such that for every $k \in \{0,\dots,n-1\}$, it holds that $d(v,n) - d(v,k) \leq c(C)$; and
\item a cycle $C$ of minimum mean cost $\mu(C) = 0$ also has $c(C) = 0$; use the above bullet to show that the right-hand side of (\ref{eq:ex-minimum-mean-cycle}) is equal to 0.
\end{itemize}

\noindent Conclude the proof of (\ref{eq:ex-minimum-mean-cycle}) by considering the case $\mu(G) \neq 0$. Show that
\begin{itemize}
\item if we transform the input $(G,c)$ into $(G,c')$ by subtracting $\mu(G)$ from the cost of every edge, then the minimum mean cost of a path of $(G,c')$ is 0, and the paths of minimum mean cost of $(G,c)$ are the same as those of $(G,c')$;
\item since relation (\ref{eq:ex-minimum-mean-cycle}) holds for $(G,c')$, then it holds also for the original input $(G,c)$.
\end{itemize}

\item[(\emph{c})] Use (\emph{a}) and the proof of (\emph{b}) to conclude that a minimum mean cost cycle $C$ in $G$ can be found in time $O(nm)$.
\label{ex:minimum-mean-cost}
\end{enumerate}

\end{enumerate}

\end{document}  