\documentclass{article}
\pagestyle{empty}

\begin{document}
\begin{center}
{\LARGE CS140: Algorithms }\\
\vspace{.1 in}
{\Large Spring 2001}\\
\vspace{.3 in}
{\large Solutions to Assignment 6}
\end{center}

\vspace{.2 in}
\begin{enumerate}

\item
A universal sink in a directed graph is a node that has an in-edge from
every other node in the graph and no out-edges.
\begin{enumerate}
\item
Prove that a directed graph has at most one universal sink.

Suppose $v$ is a universal sink and $u$ is any other node.
Then $u$ has an edge to $v$ so $u$ cannot be
a universal sink.

\item
Suppose you are only allowed to access the input graph by queries of the
from ``Is there an edge from $i$ to $j$?''  Design an algorithm to determine
if the graph has a universal sink.  You may assume the graph has $n=2^m$ nodes.
You should only need $3n-m-3$ queries in worst case.

Our algorithm operates in two stages.  In the first stage,
it rules out $n-1$ nodes as possible universal sinks. 
In the second stage, the algorithm goes
on to check whether or not the surviving node is a universal sink.

In the first stage the algorithm pairs the nodes and for
each pair $i,j$ asks the query
``Is there an edge from $i$ to $j$?''
A yes response rules out $i$ as the universal sink and a
no response rules out $j$.  The procedure continues on the survivors
until only one node, say $u$, remains.  Note that the
$n-1$ queries are made in this process and exactly $m$ of them involve
$u$.

In the second stage the algorithm checks that $u$ has an in-edge from
every other node and that it has no out-edges.  There are 2n-2 edges
to check but $m$ of them were tested in the first stage.  So the algorithm
need only make $2n-m-2$ additional queries, in worst case, to verify that $u$ is or is not
a universal sink.

The total number of queries is $3n-3-m$.




\item
Prove that $3n-m-3$ queries are necessary by giving an adversary argument.


The adversary will answer a query ``Is there an edge from $i$ to $j$?'' as
follows.
\begin{enumerate}
\item
If the query has been asked before the adversary answers consistently.
\item
Else if the previous answers the adversary has given imply that $i$ cannot be a
universal sink the adversary answers ``yes.''
\item
Else if the previous answers the adversary has given imply that $j$
cannot be a universal sink the adversary answers ``no.''
\item
Else if $i$ has been involved in more distinct queries than $j$ the adversary answers
``yes.''
\item
Else the adversary answers ``no.''
\end{enumerate}



\end{enumerate}
\item
An {\em independent set} of a graph $G$ is a subset $W$ of the vertices of $G$ such that
no two vertices in $W$ are connected by an edge in $G$.
Finding a largest independent set of an arbitrary graph is NP-hard.  The problem is
solvable in polynomial time, however, if the input is restricted to be a forest.
\begin{enumerate}
\item
Let $F$ be a forest and let $v$ be a leaf in $F$.  Prove that $v$ is in some 
largest independent set of $F$.

Let $W$ be a largest independent set of $F$ and suppose $v \not \in F$.
Let $u$ be the node adjacent to $v$ in $F$.  If $u$ is not in $W$ then
$W+\{v\}$ is a larger independent set of $F$ than $W$, which contradicts
our assumption.  So $u$ must be an element of $W$.  But then
$W-\{u\}+\{v\}$ is also a largest independent set of $F$ and it
contains $u$.

\item
Suppose I give you a black box that will find a largest independent set of a forest with
$n-1$ or fewer nodes.  Explain how to use this box to build an algorithm for finding 
 independent
sets in forests with $n$ or fewer nodes.
Be sure to describe any base cases.  (How do you handle isolated nodes?)

If $F$ has no edges then the vertices of $F$
are a largest independent set of $F$.  If $F$ has an edge then it has
a leaf, call it $v$.  Let $u$ be the node adjacent to $v$  in $F$.
Compute a largest independent set $W'$ of the forest $F-\{u,v\}$.
Then $W'+\{v\}$ is a largest independent set of $F$.

\item
How would you implement this algorithm?  Carefully describe the data structures you'll use.
You may specify the data structure used to represent the input.  Analyze the running time of
the algorithm implemented with your data structures.

(Left to the student.)
\end{enumerate}

\item
In the {\em weighted independent set} problem, the input is a graph $G$ in which each vertex
is assigned a positive weight.  The {\em weight} of an independent set $W$ is the sum
of the weights of the vertices in $W$.  The objective is to find an independent
set with largest weight.  This problem is NP-hard but can be solved in polynomial time if
we restrict the input to be a weighted tree.
\begin{enumerate}
\item
Give an example of a weighted tree $T$ for which your algorithm from problem 2
fails to find a maximum weight independent set.

(Left to the student.)
\item
Give an example of a tree $T$ rooted at some node $r$ such that the union of the maximum
weight independent sets of the children of $r$ is a maximum weight independent set 
$T$.   

(Left to the student.)
\item
Give an example of a tree $T$ rooted at some node $r$ such that the union of the maximum
weight independent sets of the children of $r$ is {\em not} a maximum weight independent set 
$T$.   Give a maximum weight independent set of this tree.

(Left to the student.)
\item
What information would you like about the subtrees of a rooted tree in order to determine
the weight of a maximum weight independent set of the tree?  (You should be able to do this with two
functions on the nodes of the tree.)

I(v):  weight of a maximum weight independent set of the tree rooted at $v$ that includes $v$.
E(v):  weight of a maximum weight independent set of the tree rooted at $v$ that excludes $v$.
\item
Design an algorithm that computes the functions you defined in the previous part.

If $v$ is a leaf then $I(v)=w(v)$ and $E(v)=0$.  If $v$ is an interior node then
$I(v) = w(v) + \sum_{\mbox{children $u$ of $v$}} E(u)$ and
$E(v) = \sum_{\mbox{children $u$ of $v$}} max(E(u),I(u))$.
\item
Show how to use this algorithm to determine the weight of a maximum weight independent set
of a tree.

Root the tree at an arbitrary node $r$.  Compute $E(v)$ and $I(v)$ at all nodes starting
at the leaves and working up to the root.  Then the weight of a maximum weight independent
set of the tree is $max(I(r),E(r))$.
\item
Show how to modify your algorithms to compute a maximum weight independent set of an input
tree.

At each node $v$ we include the set of vertices forming the independent sets corresponding
to $I(v)$ and $E(v)$.
\item
Briefly describe implementation details.  Note that an $\Theta(n)$ algorithm is possible.

Left to the student.

\end{enumerate}






\end{enumerate}
\end{document}

