\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 2}\\
Due: Tuesday, Feb 22nd, 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.
Solve Problems 1,6 and two other problems.
\noindent
\begin{myprob}
Consider the LP $\max c^T x$ such that $Ax \le b, x \in \mathbb{R}^n$ where $A$ is
a rational $m \times n$ matrix and $c$ is $n \times 1$ rational vector and $b$ is
a rational $m \times 1$ vector. Prove that if the optimum value is finite for the LP
then it is achieved by a vector $y$ that is contained in a minimal face of the polyhedron
$P = \{x \mid Ax \le b\}$. This problem is meant to be easy and it mainly to make you
read some relevant definitions.
\end{myprob}
\begin{myprob} Let $G=(V,E)$ be a bipartite graph and let $k$ be an
integer. Let $S_k$ be the set of characterstic vectors of the
matchings in $G$ of size at most $k$. Show that the following polytope
is the convex hull of the vectors in $S_k$. Alternatively, show that
it is an integral polytope.
\begin{eqnarray*}
\sum_{e \in E} x(e) & \le & k \\
x(\delta(u)) & \le & 1 \quad \quad u \in V\\
x(e) & \ge & 0 \quad \quad e \in E
\end{eqnarray*}
\iffalse
One option is to show that the constraint matrix of the above
polytope is TUM. Another is to show that all basic feasible
solutions are integral.
\fi
\end{myprob}
\begin{myprob}
Consider a bipartite graph $G=(V,E)$ with $A,B$ as the bipartition of
the vertex set $B$. A subset $X \subseteq A$ is matchable if there is matching
that saturates $X$. Suppose $X,Y$ are matchable and $|X| < |Y|$.
Show that there is a $y \in Y\setminus X$ such that $X' = X \cup
\{y\}$ is also matchable.
\end{myprob}
\begin{myprob}
Consider a bipartite graph $G=(V,E)$ with $A,B$ as the bipartition
of the vertex set $B$. For $X \subseteq A$, define $def(X)$ as $|X|
- |N(X)|$ where $N(X)$ is the set of neighbors of $X$ in
$B$. Generalize Hall's theorem to show that the size of a maximum
matching in $G$ is equal to $|A| - k$ where $k = \max_{X \subseteq
A} def(X)$. Note that $k \ge 0$ by taking $X = \emptyset$.
\end{myprob}
\begin{myprob}
Let $M$ be a matrix. Show that the maximum number of non-zero
entries in $M$ with no two in the same line (i.e., same row or same
column) is equal to the minimum number of lines that contain all
nonzero entries.
\end{myprob}
\begin{myprob}
Let $T=(V,E)$ be a rooted tree with non-negative edge costs $c: E \rightarrow \mathbb{Z}_+$.
Let $(s_1,t_1),\ldots,(s_k,t_k)$ be a given set of vertex pairs from $V \times V$.
A set of edges $A \subseteq E$ in the tree is a \emph{multicut} for the given pairs if
in the forest $T-A$ there is no path from $s_i$ to $t_i$ for any $i \in [k]$. The multicut
problem is NP-Hard even in trees. However we can solve a special case and that leads
to a $2$-approximation in trees. We will focus on the special case.
\begin{itemize}
\item Write an integer programming formulation for the multicut problem in trees
with binary variables $x_e, e \in E$.
\item Reduce the minimum vertex cover problem in a general graph to the
multicut problem in a star. Use this insight to argue that the LP relaxation is not integral
even in stars.
\item Suppose we have a special case of multicut in a tree where $s_i$
is an ancestor of $t_i$ in $T$ or the other way around (here we
fix a specific rooting). Prove that the underlying matrix in the
LP relaxation is a network matrix and hence the LP is integral.
\item {\bf Extra credit:} Use the preceding part to argue that the LP relaxation in general
trees can be used to obtain a $2$-approximation. {\em Hint:} Solve the LP and use it to
separate $s_i$ or $t_i$ from their least common ancestor by losing a factor of $2$ in the
LP cost and apply preceding part.
\end{itemize}
\end{myprob}
\end{document}