\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{\Sec}[1]{Section~{#1}}   
  \newcommand{\Btw}[1]{Insight~{#1}}
  \newcommand{\Prob}[1]{Problem~{#1}}  
  \newcommand{\R}{\ensuremath{\mathsf{R}}}  
%%%%%%%%%% 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, 2nd edition, 2023}\\
\noindent {\sf www.genome-scale.info}\\
\noindent\makebox[\linewidth]{\rule{\paperwidth}{0.4pt}}
%%%%%%%%%% header %%%%%%%%%%

\section*{Exercises for Chapter 5. Network flows}

\begin{enumerate}[label=5.\arabic*]
\item Given an arbitrary graph $G$ with a unique source $s$ and a unique sink $t$, and given a function $f : E(G) \rightarrow \mathbb{Q}$ satisfying the flow conservation property on $G$, show that

\[\sum_{y \in N^+(s)}f(s,y) = \sum_{y \in N^-(t)}f(y,t).\]
\label{ex:flow-1}
\item Let $G$ be a DAG with a unique source $s$ and a unique sink $t$, and let $f : E(G) \rightarrow \mathbb{N}$ satisfy the flow conservation property on $G$, such that the flow exiting $s$ equals $q$. Show that if there exists an integer $x$ such that, $f(e)$ is a multiple of $x$, for every $e \in E(G)$, then $f$ can be decomposed into $q/x$ paths, each of weight $x$.
\label{ex:flow-1b}

\item Show that a flow $f$ on an arbitrary graph $G$ with a unique source $s$ and a unique sink $t$ can be decomposed into at most $|E(G)|$ weighted paths or cycles. How fast can this be done?
\label{ex:flow-2}

\item In the 3-partition problem, we are given a set $A = \{a_1,\dots,a_{3q}\}$ of $3q$ positive integers, such that
	\begin{itemize}
	\item $\sum_{i = 1}^{3q}a_i = qB$, where $B$ is an integer, and
	\item for all $i \in \{1,\dots,3q\}$ it holds that $B/4 < a_i < B/2$.
	\end{itemize}
We are asked whether there exists a partition of $A$ into $q$ disjoint sets, such that the sum of the integers in each of these sets is $B$. This problem is known to be NP-hard, even when the values of the $3q$ integers in the set $A$ are bounded by a certain value not depending on $q$ (it is called \emph{strongly} NP-hard). Use a similar reduction to that in the proof of \Thm{5.3} to show that the 3-Partition problem can be reduced to the problem of decomposing a flow in a DAG into the minimum number of weighted paths.
\label{ex:flow-3}

\item Given a weighted DAG $G$, show that we can find an $s$-$t$ path whose bottleneck is maximum among all $s$-$t$ paths of $G$, in time $O(|E(G)|)$.
\label{ex:flow-4}

\item Suppose that in a flow network $N$ with a unique source and a unique sink some arcs have infinite capacity. Show that there exists a flow $f$ over $N$ of minimum cost, with the additional property that the value of $f$ on each arc without capacity is at most the sum of all arc capacities.
\label{ex:flow-12}

\item
Show that the minimum-cost circulation problem can be reduced to the minimum-cost flow problem.
\label{ex:flow-5}

\item
Given a circulation $f$ over a circulation network $N$, show that if $C$ is a cycle in the residual graph $\R(f)$ of $f$, then the circulation $f_C$ defined in \Sec{5.2} is a circulation over $N$.
\label{ex:flow-6}

\item
Given a circulation network $N = (G,\ell,u,c)$, consider the problem of finding a feasible circulation over $N$, that is, a circulation satisfying the demand and capacity constraints of $N$. Construct the circulation network $N'$ as follows:
\begin{itemize}
\item $N'$ has the same vertices as $N$;
\item for every arc $(x,y)$ of $N$, add to $N'$ two parallel arcs with demand $0$: one with cost $-1$ and capacity $\ell(x,y)$, and one with cost $0$ and capacity $u(x,y) - \ell(x,y)$.
\end{itemize}
Show that $N$ admits a feasible circulation if and only if the minimum-cost circulation over $N'$ has cost less than or equal to minus the sum of all demands of $N$. How can you obtain a feasible circulation $f$ over $N$ from a minimum-cost circulation $f'$ over $N'$?

\label{exe:flows-initial-circulation}

\item
Show that the reduction of a minimum-cost flow problem with convex costs to a standard minimum-cost flow problem from \Btw{5.2} is correct.
\label{ex:flow-7}

\item Given a DAG $G$ with a unique source $s$ and a unique sink $t$, show that we can find the maximum number of $s$-$t$ paths without common vertices (apart from $s$ and $t$) by a reduction to a maximum flow problem.

\item
In the \emph{minimum flow problem}, we are given a flow network $N$ with arc demands only, and are asked to find a flow of minimum value over $N$ satisfying all demand constraints. Show that the minimum flow problem can be solved by two applications of a maximum flow problem.
\label{ex:flow-8}

\item Show that finding a \emph{maximum-cardinality matching} in a bipartite graph can be reduced to a minimum-cost flow problem.

\item Show that, among all maximum-cardinality matchings of a bipartite graph $G$, the problem of finding one of minimum-cost can be reduced to a minimum-cost network flow problem.
\label{exe:bipartitemincostmaximummatching}

\item Suppose that you have an algorithm for solving the minimum-cost perfect matching problem in an arbitrary graph (not necessarily bipartite). Show that, given any graph $G$ with costs associated with its edges, you can use this algorithm, by appropriately transforming $G$, to find a \emph{minimum-cost maximum matching} (that is, a matching of maximum cardinality in $G$, with the additional property that among all matchings of maximum cardinality, it has minimum cost).
\label{flows:prob-minimum-cost maximum matching}

\item Consider \Prob{5.7} in which one is required to minimize instead
\[ \sum_{(x,y) \in M} c(x,y) + \alpha \sum_{y \in B}\left|\mathtt{id}(y) - d_M(y)\right|^2.\]
How do you need to modify the reduction given for \Prob{5.7} to solve this new problem? Does the resulting flow network still have  size polynomial in the size of the input? \emph{Hint.} Use the idea from \Btw{5.2}.
\label{exe:flow-mc-momorf-square}


\item Show that the problem of finding a minimum-cost disjoint cycle cover in an undirected graph can be reduced to the problem of finding a minimum-cost disjoint cycle cover in a directed graph.
\label{ex:flow-10}

\item An \emph{edge cover} of an undirected graph $G$ is a set of edges covering all the vertices of $G$.
\begin{itemize}
\item Show that a minimum-cost edge cover in a bipartite graph can be solved by a minimum-cost flow problem.
\item Show that a minimum-cost edge cover in an arbitrary graph $G$ can be reduced to the problem of finding a maximum-weight matching in $G$.
\end{itemize}
\label{ex:flow-11}

\section*{Additional exercises not in the book}

\item Give an example of a directed acyclic graph which admits two decomposition into weighted paths, each with a different number of paths.

\item Give an example of a directed graph $G$ (not acyclic) with unique source $s$ and unique sink $t$, and of a flow $f$ in $G$, such that $f$ cannot be decomposed into a set of weighted $s$-$t$ paths.

\item Given a directed graph $G$ with a unique source $s$ and unique sink $t$, in which every arc $(x,y)$ has a capacity $u(x,y)$, construct a minimum-cost flow network $N$ in which every arc $(x,y)$ of $G$ has demand 0, capacity $u(x,y)$ and cost $-1$. Add the arc $(s,t)$ with demand 0, capacity $\infty$ and cost 0, and set the flow value to $\infty$. Give an example which disproves the following claim: the minimum-cost flow in $N$ is a maximum flow in $G$ with capacity function $u$.

\item Give an example of a bipartite graph $G$, and a non-integer-valued flow $f$, feasible for the network built for the minimum-cost perfect matching problem on $G$, such that $f$ does not induce a matching in $G$.

\item Give an example of a directed acyclic graph $G$ and of a non-integer-valued flow $f$, feasible for the network built for the minimum-cost minimum path cover problem on $G$, such that $f$ does not induce an optimal solution in $G$.

\item Consider the following simpler variant of the minimum-cost minimum path cover problem. Given a DAG $G = (V,E)$ with unique source $s$ and unique sink $t$, a cost function $c : E \rightarrow \mathbb{Q}_+$, and an integer $k$, find $k$ $s$-$t$ paths $P_1,\dots,P_k$ forming a path cover of $G$ (i.e.~each vertex of $G$ belongs to some $P_i$) and minimizing $\sum_{i = 1}^{k}\sum_{(x,y) \in P_i} c(x,y)$. Solve this problem by a reduction to a minimum-cost flow problem.

\item Consider the following problem: given a directed graph $G$, find the minimum number of paths (possibly with repeated vertices) that cover all the vertices of $G$. Give an example of a directed graph where this number is two. Show that this problem can be reduced to a minimum-cost flow problem.

\end{enumerate}

\end{document}  