\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{times}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{latexsym}
\newcommand{\myparskip}{6pt}
\parskip \myparskip
\newtheorem{lemma}{Lemma}[section]
\newtheorem{theorem}[lemma]{Theorem}
\newtheorem{assumption}[lemma]{Assumption}
\newtheorem{definition}[lemma]{Definition}
\newtheorem{corollary}[lemma]{Corollary}
\newtheorem{prop}[lemma]{Proposition}
\newtheorem{claim}[lemma]{Claim}
\newtheorem{remark}[lemma]{Remark}
\newtheorem{prob}{Problem}
\newenvironment{myprob}{\begin{prob} \em}{\end{prob}}
\newcommand{\opt}{\mbox{\sc opt}}
\newcommand{\eps}{\epsilon}
\begin{document}
\setlength{\fboxrule}{.5mm}\setlength{\fboxsep}{1.2mm}
\newlength{\boxlength}\setlength{\boxlength}{\textwidth}
\addtolength{\boxlength}{-4mm}
%\begin{center}\framebox{\parbox{\boxlength}{%\bf
\begin{center}
{\bf Spring 2022, CS 586/IE 519: Combinatorial Optimization\\
Homework 1}\\
Due: Thursday, Feb 3rd, 2022
\end{center}
%}}\end{center}
\vspace{5mm}
\noindent {\bf Instructions and Policy:}
Each person should write up their own solutions independently. You
need to indicate the names of the people you discussed a problem
with. Solutions to most of these problems can be found from one source
or the other. Try to solve on your own first, and cite your sources if
you do use them.
\noindent
Please write clearly and concisely. Refer to known facts. You should
try to convince us that you know the solution, as quickly as possible.
Submit solutions to Problems 2, 4, 6. And try so solve others but do
not
submit.
\noindent
\begin{myprob}
Let $G=(V,E)$ be a directed graph and let $\ell : E \rightarrow
\mathbb{R}$ be edge lengths (which can be negative).
A directed cycle $C$ in $G$ is a negative length cycle if
$\sum_{e \in C} \ell(e) < 0$. How can we convince ourselves that
$G$ does not have a negative length cycle? We say that
a function $\pi: V \rightarrow \mathbb{R}$ is a valid potential if
for each edge $(u,v) \in E$ we have $\pi(v) \le \pi(u) + \ell(u,v)$.
\begin{itemize}
\item Prove that if $G$ has a negative length cycle than there is
no valid potential.
\item Prove that if there is a valid potential then there is no
negative length cycle in $G$.
\item How can you use the Bellman-Ford algorithm to obtain a valid
potential if $G$ does not have a negative length cycle?
\item Suppose you have computed a valid potential $\pi$ in $G$. For
each edge $(u,v)$ define the reduced cost/length of $(u,v)$ to be
$\ell'(u,v) = \ell(u,v) + \pi(u) -\pi(v)$ which is non-negative.
Suppose you want to find shortest path lengths from a node $s$ to
every other node. Show how you can compute shortest paths using
the reduced costs via Dijkstra's algorithm and obtain the actual
shortest paths in $G$. Thus, once we have potentials, finding
single-source shortest paths can be reduced to the setting of
non-negative edge lengths.
\end{itemize}
\end{myprob}
\begin{myprob}
Let $G=(V,E)$ be an undirected graph. We use $\delta(A)$ to denote
that set of edges with one end point in $A$ and the other in $V-A$.
For two disjoint sets of vertices $A,B \subset V$ we use $E(A,B)$ to
denote the set of edges with one end point in $A$ and another in
$B$.
\begin{itemize}
\item Prove that for any $A, B \subseteq V$,
$$|\delta(A)| + |\delta(B)| = |\delta(A \cap B)| +
|\delta(A \cup B)| + 2|E(A-B,B-A)|$$
\item A real-valued set function $f: 2^V \rightarrow \mathbb{R}$ is
called submodular iff $f(A) + f(B) \ge f(A \cup B) + f(A \cap B)$
for all $A, B \subseteq V$. Prove that for any graph $G=(V,E)$
the function $f(A) = |\delta(A)|$ is submodular. Note that $f$ is
also symmetric.
\item Suppose $G=(V,E)$ be a directed graph and now consider the
function $f(A) = |\delta^+(A)|$ where $|\delta^+(A)|$ is the
number of edges that leave $A$ (with the tail in $A$ and head in
$V-A$). Prove that $f$ is submodular.
\item {\bf Not to submit:} A hypergraph $G=(V,E)$ consists of a finite vertex set $V$ and
a set of hyperedges $E$ where each hyperedge $e \in E$ is a subset
of $V$, that is $e \subseteq V$. Graphs are the special case when
each hyperedge has two vertices. For a given hypergraph $G$
and a set $A \subseteq V$ let $\delta(A)$ denote the set of
hyperedges
that contain (at least) one node in $A$ and (at least) one in $V-A$.
Prove that $f(A) = |\delta(A)|$ is submodular.
\end{itemize}
\end{myprob}
\begin{myprob}
Let $G=(V,E)$ be an undirected graph. Let $u,v,w$ be three distinct
nodes. Describe an efficient algorithm to check if there is
a simple path from $u$ to $v$ that contains $w$. What is the running
time of your algorithm? {\em Hint:} Reduce to disjoint paths/flow.
Note that the problem in directed graphs is NP-Complete!
\end{myprob}
\begin{myprob}
Let $G=(V,E)$ be a directed graph with integer edge capacities, and
let $s,t$ be distinct nodes. The Ford-Fulkerson augmenting path
algorithm finds a maximum flow $f$ and proof of the maxflow-mincut
theorem is based on showing the following. Suppose there is no
$s$-$t$ path in the residual graph $G_f$. Let $A$ be the set of
nodes reachable from $s$ in the residual graph $G_f$. The proof
shows that in this case $|\delta^+(A)| = |f|$ and hence we have
optimality of the flow and the cut. It is easy to observe that a
graph can have many $s$-$t$ mincuts. However one can prove that
there is a \emph{unique} minimal $s$-$t$ cut and a unique maximal
mincut. To be precise we say that a set $S$ is a minimal mincut if
there is no $S'$ such that $S' \subset S$ and $S'$ is also a
mincut. Minimality does not necessarily imply uniqueness since there
can be two mincuts $S, S'$ such that neither is a subset of the
other.
\begin{itemize}
\item Prove that if $A$ and $B$ are $s$-$t$ mincuts then $A \cap B$
and $A \cup B$ are also $s$-$t$ minimum cuts. You can use submodularity or
prove it in other ways.
\item Argue that if $f$ is a maximum flow then the set of reachable
nodes from $s$ in $G_f$ is the unique minimal $s$-$t$ cut.
\item How would you find the unique maximal
$s$-$t$ cut given a maximum flow $f$?
\end{itemize}
\end{myprob}
\begin{myprob}
Let $G=(V,E)$ be a $d$-regular bipartite graph.
\begin{itemize}
\item Prove that $G$ has a perfect matching. You
can use flows or Hall's theorem or any other method.
\item Prove that $G$ can be edge-colored with
$d$ colors. By an edge-coloring we mean a coloring of edges such
that no two edges that intersect at a node have the same color.
\item Prove that every bipartite graph with maximum degree $d$ can
be edge-colored with $d$ colors.
\item Give a simple example of a $2$-regular non-bipartite graph
that cannot be edge-colored with $2$ colors.
\end{itemize}
\end{myprob}
\begin{myprob}
Let $G=(V,E)$ be a directed graph with edge lengths/costs $c: E
\rightarrow \mathbb{Z}$ (could be negative). Let $s, t$ be distinct
nodes in $G$. There are several ways to write an LP relaxation for
the $s$-$t$ shortest path. One way is to view an $s$-$t$ shortest
walks as a minimum cost set of edges in $G$ that connect $s$ to $t$.
Letting $x_e$ denote a variable for each edge $e \in E$ we express
connectivity by asking for at least one edge to cross any
cut $(S,V-S)$ such that $s \in S, t \not \in S$.
\begin{align*}
\min \sum_{e \in E} c_e x_e && \\
\sum_{e \in \delta^+(S)} x_e & \ge 1 \quad s \in S, t \not \in S \\
x_e &\ge 0 \quad e \in E
\end{align*}
Note that the LP has an exponential number of constraints.
\begin{itemize}
\item Argue that the LP is feasible iff there is an $s$-$t$ path in $G$.
\item Write the dual LP.
\item Suppose all the edge lengths are non-negative. Argue
that there is a feasible solution to the dual of value equal to the shortest path
distance from $s$ to $t$. {\em Hint:} Use shortest path distances from $s$ to
find a setting of dual values.
\end{itemize}
\end{myprob}
\iffalse
\begin{eqnarray*}
\min \sum_{e \in E} c_e x_e && \\
\sum_{e \in \delta^+(S)} x_e & \ge & 1 \quad s \in S, t \not \in S \\
x_e &\ge & 0 \quad e \in E
\end{eqnarray*}
\fi
\iffalse
\begin{myprob} A \textit{circulation} in a flow network is a flow of value $0$. A circulation has no source or sink vertex. In the \textit{minimum cost circulation} problem we are given a directed graph $G = (V,E)$, where each edge has a capacity given by $c: E \rightarrow \mathbb{R}_+$ and a cost given by $w: E \rightarrow \mathbb{R}$. The goal is to find a feasible circulation with minimum total cost.
\begin{itemize}
\item Write an LP for computing a min-cost circulation
in $G$.
\item Derive the dual of the LP you found in the previous part.
\end{itemize}
\end{myprob}
\begin{myprob} Suppose we are given $n$ linear inequalities of the form $a_i x + b_i y \leq c_i$. Collectively, these $n$ inequalities describe a convex polygon $P$ in the plane.
\begin{itemize}
\item Write an LP for computing the largest axis-aligned square which is entirely contained in $P$ (axis-aligned means that the sides of the square are horizontal and vertical).
\item Write an LP for computing the largest axis-aligned rectangle which is entirely contained in $P$.
\item Write an LP for computing the largest circle which is entirely contained in $P$.
\end{itemize}
\end{myprob}
\fi
\end{document}