\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{CS5800}{Algorithms}{Spring 2011}{22 April 2011}{28}

\begin{center}
\Large{\bf Sample Solution to Problem Set 7}
\end{center}

{\bf 1. Problem 8.22 of text.}

{\bf Answer:}
\begin{itemize}
\item [a)] One can verify if $E' \subseteq E$ is a feedback arc set
  (FAS) in polynomial time by removing $E'$ from $E$ and using BFS to
  check if there is a cycle in $(V,E-E')$.

So we can prove FAS is in $NP$.

\item [b)]

Suppose $C$ is a vertex cover of $G$ with size $b$. For any vertex
$v_i \in C$, suppose its corresponding vertices in $G'$ are $w_i$
and $w'_i$, so we add the edge $(w_i,w'_i)$ into $E'$.

After we process every vertex in $C$, the edge set $E'$ we get is
exactly the FAS of $G$ with size $b$. It is because for vertices $w_i$
and $w'_i$, when we remove the edge $(w_i,w'_i)$, all the edges that
connect to $w_i$ could not be in any cycle, since $w_i$ has no
out-edge.

Similarly all the edges that connect to $w'_i$ could not be in any
cycle either, since $w'_i$ has no in-edge.

\item [c)]

For any edge $(v_i,v_j)$ in $G$, suppose its corresponding vertices
in $G'$ are $w_i$, $w'_i$, $w_j$ and $w'_j$, and the corresponding
edges are $(w_i,w'_i)$, $(w_j,w'_j)$, $(w'_i,w_j)$ and $(w'_j,w_i)$.

\begin{itemize}
\item If $E'$ is a FAS of $G$ with size $b$, obviously there is at least
one edge of the above four edges that is in $E'$, otherwise it will
form a cycle.

\item Moreover edge $e$ has at least one vertex that belongs to
$(w_i,w_j)$. If $w_i$ is the vertex of $e$, we will add $v_i$ into
$C$, otherwise we add $v_i$ into $C$.
\end{itemize}

After the above processing, $C$ is a vertex cover of $G$ with size
(at most) $b$.

\end{itemize}

\end{document}
