\documentclass[11pt]{article}
\input{../../preamble}
\usepackage{amsmath, latexsym}
\begin{document}
\problemset{12}{November 21, 2014}{12}{December 5, 2014}
\begin{enumerate}
\item (21 points) Prove that the following problems are NP-complete.
\begin{enumerate}
\item (7 points) In the decision version of the {\em maximum clique} problem, we are given as input a graph $G=(V,E)$ and a number $B$. A {\em clique} is a subset of vertices $S$ such that for all
$i, j \in S$, there is an edge $(i,j) \in E$. We must decide whether there is a clique $S$ with $|S| \geq B$.
\item (7 points) Given a graph $G=(V,E)$, a {\em vertex cover} is a set of vertices $S$ such that for all $(i,j) \in E$, either $i \in S$ or $j \in S$ (or both). In the decision version of the vertex cover, we are given a graph $G=(V,E)$ and a bound $B$, and we must decide if the graph contains a vertex cover $S$ with $|S| \leq B$.
\item (7 points) A {\em dominating set} of an undirected graph $G$ is a set
of vertices $S$ such that for all $u \notin S$, there is some edge
$(u,v)$ with $v \in S$. In the decision version of this problem,
we are given the undirected graph and a bound $B$ and must decide
if there exists a dominating set $S$ such that $|S| \leq B$.
\end{enumerate}
\item (30 points) In recitation on November 12, you discussed the minimum-cost spanning tree problem and showed that a particular algorithm gives an optimal solution to the problem by giving a dual solution to a linear programming relaxation of the problem that has the same value. Here we will see another linear programming relaxation of the problem also works.
We could consider a formulation similar to that we used for the traveling salesman problem. In that formulation, we considered sets of edges $\delta(S) = \{(u,v) \in E: u \in S, v \notin S\}$, where $S \subset V$. Consider the following linear program:
\begin{eqnarray*}
\mbox{Min } \sum_{e \in E} c_e x_e\\
\sum_{e \in \delta(S)} x_e & \geq & 1 \qquad \forall S \subset V, S \neq \emptyset\\
x_e & \geq & 0 \qquad \forall e \in E.
\end{eqnarray*}
\begin{enumerate}
\item (5 points) Argue that this is a linear relaxation of the minimum-cost spanning tree problem; that is, given an minimum-cost spanning tree $T$, if we set $x_e = 1$ for all $e \in T$, this is a feasible solution for the LP that has no greater cost than $T$.
\item (5 points) Show that there are graphs for which the LP has cost strictly smaller than that of the optimal spanning tree (Hint: there is an example on three vertices).
\end{enumerate}
Now let ${\cal P}$ be a partition of the vertex set; i.e. ${\cal P} = \{P_1,\ldots,P_k\}$ such that $P_i \cap P_j = \emptyset$ if $i \neq j$ and $\bigcup_i P_i = V$. Given any ${\cal P}$, if we sum together the constraints of the LP above associated with $P_i \in {\cal P}$, we have that
$$\sum_{P_i \in {\cal P}} \sum_{e \in \delta(P_i)} x_e \geq |{\cal P}|.$$ Yet we can say something stronger than this.
\begin{enumerate}
\item[(c)] (5 points) Prove that for any spanning tree $T$, if $x_e = 1$ for all $e \in T$, then for any partition ${\cal P}$, $$\sum_{P_i \in {\cal P}} \sum_{e \in \delta(P_i)} x_e \geq 2|{\cal P}|-2.$$
\end{enumerate}
Now consider the following linear program.
\begin{eqnarray*}
\mbox{Min } \sum_{e \in E} c_e x_e\\
\sum_{P_i \in {\cal P}} \sum_{e \in \delta(P_i)} x_e & \geq & 2|{\cal P}|-2 \qquad \forall \mbox{ partitions } {\cal P}\\
x_e & \geq & 0 \qquad \forall e \in E.
\end{eqnarray*}
\begin{enumerate}
\item[(d)] (5 points) Argue that the linear program above is a linear programming relaxation of the minimum-cost spanning tree problem.
\item[(e)] (10 points) Using the same minimum-cost spanning tree algorithm that you did in class, show that the algorithm produces the optimal solution by using the linear programming relaxation above and its dual. This also proves that the linear program always returns a solution of cost equal to the minimum-cost spanning tree.
\end{enumerate}
\end{enumerate}
\end{document}