\documentclass[11pt]{article}
\usepackage{program}


\title{6.046 Problem Set 9}
\author{Chris Laas: Section G}
\date{April 27, 2000}

\pagestyle{myheadings}
\markright{Chris Laas: Section G \hfil 6.046J/18.410J \hfil 4/27/2000}

\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{\arabic{enumii}.}
\NumberProgramstrue
\def\RETURN{\keyword{return}\ }
\def\MOD{\mbox{mod}\ }
\def\text#1{\mbox{ #1 }}
\def\AND{\mbox{\bf\ and }}
\def\OR{\mbox{\bf\ or }}
\def\TRUE{\mbox{\bf true}}
\def\FALSE{\mbox{\bf false}}
\def\choice#1{\left\{ \begin{array}{ll} #1 \end{array} \right.}
\def\({\left(}
\def\){\right)}
\def\[{\left[}
\def\]{\right]}



\begin{document}
\maketitle






\section*{Problem 9-1}

The maximum matching in trees problem exhibits optimal substructure;
thus, the algorithm I develop will be a dynamic programming algorithm.

First, I will demonstrate the recursive optimal substructure of the
problem.  Let $M$ be a maximum matching for a tree $T$ rooted at the
node $r$, and let $u$ be a direct child of $r$.  There are two cases:
$(r,u) \in M$, and $(r,u) \notin M$.

If $(r,u) \notin M$, then $M_u = M \cap E[T_u]$ is a maximum matching
for the subtree $T_u$ of $T$ rooted at $u$.  For, if we assume that
there exists a matching $M'_u$ of $T_u$ with more edges than $M_u$,
then $M - M_u \cup M'_u$ would also be a matching of $T$ with more
edges than $M$; thus, $M$ would not be maximal, which is a
contradiction.

If, on the other hand, $(r,u) \in M$, then, for any child $v$ of $u$,
$(u,v) \notin M$, and $M_u = M \cap E[T_u]$ is a maximum matching of
the subtree $T_v$ of $T$ rooted at $v$.  The fact that $(u,v) \notin
M$ is clear, since there can be only one edge in $M$ with $u$ as an
endpoint.  And, if we assume that there exists a matching $M'_u$ of
$T_v$ with more edges than $M_u$, then $M - M_u \cup M'_u$ would be a
matching of $T$ with more edges than $M$; thus, $M$ would not be
maximal, which is a contradiction.

Thus, there are two cases for a maximum matching $M$ of the tree $T$
rooted at $r$.  In the first case, none of $r$'s children are
connected to $r$ via an edge in $M$, and all of $r$'s subtrees are
maximally matched by their edges in $M$.  In the second case, there
exists a child $u$ of $r$ such that $(r,u) \in M$: then, no other
child of $r$ shares an edge with $r$ in $M$; all of $r$'s subtrees
rooted at children other than $u$ are maximally matched by their edges
in $M$; and, all of $u$'s subtrees are maximally matched by their
edges in $M$.

For {\em any} node $r$ in a tree $T$, let us denote the number of
edges in a maximum matching of the subtree $T_r$ by $m(r)$.  Then we
may summarize the above theorem by the recursion
$$ m(r) = \max\( \begin{array}{l}
                 \sum_{u \in children(r)} m(u),                    \\
                 \max \left\{ 1 + \sum_{u' \in children(r)-\{u\}} m(u')
                              + \sum_{v \in children(u)} m(v)
                              \mbox{\ for all\ } u \in children(r) \right\}
                 \end{array}
              \) $$
If we define $s(u) = \sum_{v \in children(u)} m(v)$, we can simplify
the above expression to the following form:
\begin{eqnarray*}
m(r) & = & \max\( s(r), \max \left\{ 1+(s(r)-m(u))+s(u)
                                     \mbox{\ for all\ } u \in children(r)
                             \right\} \) \\
     & = & s(r) + \max\( 0, \max \left\{ 1+s(u)-m(u)
                                         \mbox{\ for all\ } u \in children(r)
                             \right\} \)
\end{eqnarray*}

Naturally, the base case for the recursion is $s(u) = 0$ if $u$ has no
children.  This defines $s$ and $m$ over the entire tree;
$m(|root|[T])$ gives the number of edges in the maximum matching of
the tree $T$.

The formulas for $m(u)$ and $s(u)$ depend only on their values on the
subtree rooted at $u$; thus, they can be computed via a preorder
traversal of the tree.  We will also keep track of another per-node
field $e[u]$, which we will use to recontruct the maximum matching: if
the calculated maximum matching of the subtree $T_u$ contains no edge
$(u,v)$, then $e[u] = |nil|$, and if it contains one edge $(u,v)$,
then $e[u] = v$.

\begin{program}
|Maximum-Matching-In-Tree|(T)
\quad\tab |Maximum-Matching-Visit|(|root|[T])
          \RETURN |Maximum-Matching-Reconstruct|(|root|[T])
\end{program}

\begin{program}
|Maximum-Matching-Visit|(u)
\quad\tab s[u] \gets 0
          \Delta m \gets 0
          e[u] \gets |nil|
          \FOR \mbox{\ each child $v$ of $u$\ }
              |Maximum-Matching-Visit|(v)
              s[u] \gets s[u] + m[v]
              \IF \Delta m < 1+s[v]-m[v]
                 \THEN \Delta m \gets 1+s[v]-m[v]
                       e[u] \gets v
                       \untab%
                 \untab%
              \untab%
         m[u] \gets s[u] + \Delta m
\end{program}

\begin{program}
|Maximum-Matching-Reconstruct|(u)
\quad\tab M \gets \emptyset
          \FOR \mbox{\ each child $v$ of $u$\ }
              \IF v \neq e[u]
                 \THEN M \gets M \cup |Maximum-Matching-Reconstruct|(v)
                      \untab%
                 \untab%
              \untab%
          \IF e[u] \neq |nil|
             \THEN \FOR \mbox{\ each child $v$ of $e[u]$\ }
                       M \gets M \cup |Maximum-Matching-Reconstruct|(v)
                       \untab%
                   \RETURN M \cup \{(u,e[u])\}
             \ELSE \RETURN M
\end{program}

Correctness of the above pseudocode is trivial, given the theorems
proven above.  $|Maximum-Matching-Visit|$ computes all the values for
$m$ on the subtree rooted at a node, and saves the information needed
to reconstruct a maximum matching in $e$; the pseudocode is a direct
implementation of the recursion formula.
$|Maximum-Matching-Reconstruct|$ merely uses the information in $e$ to
reconstruct the set of edges in the maximum matching of the entire
tree; again, the form is dictated directly by the recursion formula.
Termination is guaranteed because both are preorder traversals of the
tree (except that $|Maximum-Matching-Reconstruct|$ skips node $e[u]$
when $e[u] \neq |nil|$).

The run time of the algorithm is quite clearly linear in the number of
nodes:  $|Maximum-Matching-Visit|$ takes $\Theta(n)$ steps, as a
normal preorder traversal of the tree, and
$|Maximum-Matching-Reconstruct|$'s runtime is obviously bounded by
$O(n)$, as a preorder traversal which may skip some nodes.  Thus the
whole algorithm runs in $\Theta(n)$ time.

\newpage







\section*{Problem 9-2}

The algorithm's strategy is to perform a binary search on the possible
bottleneck weights; all of the edges are first sorted by weight into
an array $A$, and then the smallest segment $A[1 \rdots k]$ is found
such that a maximal matching using only those edges has the same
number of edges as a maximal matching on the whole graph.

The preconditions to $|Binary-Search-Bottle-Neck-Matching|$ are:
\begin{itemize}
\item $A$ should be an array containing all edges in $G$, sorted in
increasing order by weight.
\item $|maxmatch|$ is the number of edges in a maximal matching on the
whole graph.
\item There exists some $k$ such that $p \leq k \leq q$ and that the
number of edges in a maximal matching using only edges in
$A[1 \rdots k]$ is equal to $|maxmatch|$.
\end{itemize}

The postcondition is that $|Binary-Search-Bottle-Neck-Matching|$
returns a maximal matching of $G$ with minimum bottleneck weight.

\begin{program}
|Bottle-Neck-Matching|(G)
\quad\tab m \gets \|E[G]\|
          A \gets |Heapsort|_{w[G]}(E[G])
          M \gets |Maximal-Matching|(G)
          |maxmatch| \gets \|M\|
          \RETURN |Binary-Search-Bottle-Neck-Matching|(G, A, |maxmatch|, 0, m)
\end{program}

\begin{program}
|Binary-Search-Bottle-Neck-Matching|(G, A, |maxmatch|, p, q)
\quad\tab k \gets \left\lfloor \frac{p+q}{2} \right\rfloor
          G_k \gets (V[G], A[1 \rdots k])
          M \gets |Maximal-Matching|(G_k)
          \IF p = q
             \THEN \RETURN M
                   \untab%
             \untab%
          \IF \|M\| = |maxmatch|
             \THEN \RETURN |Binary-Search-Bottle-Neck-Matching|(G, A, |maxmatch|, p, k)
             \ELSE \RETURN |Binary-Search-Bottle-Neck-Matching|(G, A, |maxmatch|, k+1, q)
\end{program}

The first four lines of $|Bottle-Neck-Matching|$ ensure that the first
two preconditions are satisfied; the third is satisfied because any
matching at all must have between 0 and $m$ edges, inclusive.

$|Binary-Search-Bottle-Neck-Matching|$ performs a very simple binary
search algorithm; the choice of $k$ guarantees that the range $p
\rdots q$ always decreases (guaranteeing termination, since
termination occurs when $p = q$), and the execution of
$|Maximal-Matching|$ determines in which subrange the bottle neck
match is.  Precondition 3 is guaranteed, because if there exists a
maximal matching among edges $1 \rdots k'$, for $p \leq k' \leq k$, then
there clearly exists a maximal matching among edges $1 \rdots k$.

The subroutine $|Maximal-Matching|$, which runs in $O(\sqrt{n} m)$
time, is run $O(1) + O(\lg m) = O(\lg n)$ times; the heapsort at the
beginning takes $O(n \lg n)$ time.  Thus, the total run time is
$O(n \lg n + \sqrt{n} m \lg n) = O(\sqrt{n} m \lg n)$.

\newpage







\section*{Problem 9-3}
\begin{enumerate}

\item%(a)

We are given the DAG $G = (V,E)$, such that $V = (v_1,\dots,v_n)$.
To solve this problem, first form a network $G' = (V',E')$ as follows:
$$ V' = \{s,t\} \cup \{x_1,\dots,x_n\} \cup \{y_1,\dots,y_n\} $$
$E'$ is defined by:
\begin{itemize}
\item $(s,x_i) \in E'$ for all $1 \leq i \leq n$
\item $(y_i,t) \in E'$ for all $1 \leq i \leq n$
\item $(x_i,y_i) \in E'$ if and only if $(v_i,v_j) \in E$
\end{itemize}
The capacity of all edges is 1.

To show that the minimum number of paths which cover $V$ in $G$ is
equal to $n - F$ where $F$ is the maximum total flow of $G'$, we
show that there is a one-to-one correspondence between existence of a
flow with total flow $F$ and existence of a set of $n - F$
covering paths.

If there exists a flow $f$ with total flow $F$, then we can construct
a covering set of paths by taking all edges $(v_i,v_j)$ such that
$(x_i,y_j)$ has a flow of one, and connecting them into paths wherever
possible.  Since at most one unit can flow through any $x_i$, there
can exist at most one edge $(v_i,v_j)$ in the set for any $v_i$; thus,
all the connected components of this set are paths.  Now, since the
total flow in $G'$ is $F$, there must exist $n - F$ vertices $x_i$
with no flow through them; since the graph is acyclic, each of these
must correspond to the endpoint $v_i$ of a path in the set of paths we
have constructed.  (Or it may be a lone node, which is the same
thing.)  Thus, there must exist a total of $n - F$ paths in the path
set we have constructed.

On the other hand, let us assume we have a set of edges $S$ which
comprise $k$ paths in $G$; we can easily construct a flow $f$ through
$G'$ by setting the flow to 1 on any edges $(s,x_i)$, $(x_i,y_j)$, or
$(y_j,t)$ such that the edge $(v_i,v_j)$ is in $S$.  Since $S$
consists entirely of paths, no node $v_i$ has more than one
predecessor or successor in $S$; thus, no $x_i$ will have more than
one unit of outflow, nor will any $y_i$ have more than one unit of
inflow, maintaining the flow constraints.  Since there are exactly $k$
endpoint nodes in $S$, there are exactly $k$ nodes $x_i$ with no
outflow, and all other $x_i$ have one unit of outflow; thus, the total
flow of the graph will be $F = n - k$.

Thus, in any case where there exists a flow with total flow $F$, there
exists a set of $n - F$ covering paths, and vice versa; thus, the
minimum number of covering paths in $G$ is equal to $n - F = \|V\| - F$
where $F$ is the maximum total flow of the network $G'$.


\item%(b)

Yes: if there existed a cycle in the graph, then there could exist a
path in the graph with no endpoint.  This would make the algorithm
invalid, since it depends on counting endpoints to count paths,
essentially.


\item%(c)

The number of nodes in $G'$ is equal to $2n+2$, and the number of
edges is $2n+m$, where $n = \|V\|$ and $m = \|E\|$.  Thus
$\|V'\| = O(n)$ and $\|E'\| = O(m)$.

The run time of the Ford-Fulkerson algorithm for finding maximum flows
is $O(F \|E'\|)$; since the flow is limited by the number of
capacity-one edges $(s,x_i)$, the maximum flow is $F = \|V\|$.  Thus,
the run time of this algorithm is $O(nm)$.


\end{enumerate}
\newpage







\section*{Problem 9-4}
\begin{enumerate}

\item%(a)

We are given a flow network $G = (V,E)$ with capacity function $c$ and
many sources $s_i$ and sinks $t_i$.  To construct the conventional
max-flow network $G' = (V',E')$ with capacity function $c'$:

Add a supersource $s'$ and supersink $t'$, i.e. let the set of
vertices be $V' = V \cup \{ s', t' \}$; add infinite-capacity edges
from the supersource to all sources, and from all sinks to the
supersink, so that the set of edges is
$$ E' = E \cup \{ (s',s_i) \mbox{\ for all sources $s_i$\ } \}
          \cup \{ (t_i,t') \mbox{\ for all sinks $t_i$\ } \} $$
and the capacity function is given by $c'(s',s_i) = \infty$ for all
$s_i$, $c'(t_i,t') = \infty$ for all $t_i$, and $c'(u,v) = c(u,v)$ 
for all $(u,v) \in E$.

The construction of this new graph is clearly polynomial time, since
only 2 vertices and at most $2n$ edges are created.  Now run a
standard polynomial-time max-flow-finding algorithm to generate the
max-flow function $f'$ for $G'$.  To construct the max-flow function
$f$ for $G$ from $f$, let $f(u,v) = f'(u,v)$ for all $(u,v) \in E$.

Clearly the flow thus calculated maximizes the total flow from all the
sources to all the sinks, since that total flow is exactly the flow
that comes out of the supersource.


\item%(b)


We are given a flow network $G = (V,E)$ with edge capacity function
$c_e$ and vertex capacity function $c_v$; number the vertices so that
$V = \{ v_1, \dots, v_n \}$.  To construct the conventional max-flow
network $G' = (V',E')$ with capacity function $c'$:

Let the set of vertices be
$V' = \{ x_1, \dots, x_n \} \cup \{ y_1, \dots, y_n \}$.  Construct
the set of edges thus:
\begin{itemize}
\item $(y_i, x_j) \in E'$ if and only if $(v_i, v_j) \in E$.
\item $(x_i, y_i) \in E'$ for all $i \in \{1, \dots, n\}$.
\item $(x_i, y_j) \notin E'$ if $i \neq j$.
\end{itemize}
Let the capacity function be defined by:
\begin{eqnarray*}
c'(y_i, x_j) & = & c_e(v_i, v_j) \\
c'(x_i, y_i) & = & c_v(v_i)      \\
\end{eqnarray*}

The construction of this new graph is clearly polynomial time, since
there are $2n$ vertices and $m+n$ edges in the new graph.  Now run a
standard polynomial-time max-flow-finding algorithm to generate the
max-flow function $f'$ for $G'$.  To construct the max-flow function
$f$ for $G$ from $f'$, let $f(v_i, v_j) = f'(y_i, x_j)$ for all
$(v_i, v_j) \in E$.

The maximum flow thus calculated obeys both the edge capacity function
and the vertex capacity function, since all the flow going into any
node $x_i$ must go through the single outward edge $(x_i,y_i)$ and
come out at the node $y_i$.




\end{enumerate}
\newpage







\section*{Problem 9-5}
\begin{enumerate}

\item%(a)

 \begin{enumerate}
 \item %1.
 ``Consider an unweighted undirected graph $G = (V,E)$.  Given two
 vertices $a,b \in V$ and a positive integer $k$, does there exist a
 simple path from $a$ to $b$ of length less than or equal to $k$?''

 \item %2.
 Clearly, if the optimization problem is solvable in polynomial time,
 we can solve the decision problem in polynomial time, since there
 exists a simple path of length less than or equal to $k$ if and only
 if the shortest path has length less than or equal to $k$.

 On the other hand, assume that we can solve the decision problem in
 polynomial time.  Then, using it as a subroutine, we can perform a
 binary search for the shortest path length, starting with
 $1 \rdots \|V\|$ as the bounds for $k$.  (No simple path can have
 length greater than $\|V\|$.)  The size of the input to the decision
 problem is $O(n^2 + \lg k)$, which, since $k = O(n)$ in this case,
 reduces to $O(n^2)$; assuming the run time of the decision
 algorithm is $O(f(n))$, the run time of this optimization algorithm will
 be $O(f(n) \lg n)$, which is polynomial.

 \item %3.
 Given a set of edges in $E$, we can easily check whether there are
 $k$ edges; and we can check whether it is a simple path from $a$ to
 $b$ by the following algorithm:
 \begin{program}
 |Is-Simple-Path|(S, a, b)
 \quad\tab \IF S = \{(a,b)\}
              \THEN \RETURN \TRUE
                   \untab%
              \untab%
           \IF \mbox{\ there exists a unique edge $(a,u) \in S$\ }
              \THEN \RETURN |Is-Simple-Path|(S - \{(a,u)\}, u, b)
              \ELSE \RETURN \FALSE
 \end{program}
 This verifying algorithm clearly runs in polynomial time in the
 length of the path; it is correct because a set of edges $S$ is a
 simple path from $a$ to $b$ if and only if there exists a unique
 vertex $u$ such that $S = \{(a,u)\} \cup S'$ and $S'$ is a simple
 path from $u$ to $b$ (or $S' = \emptyset$ and $u = b$).

 \end{enumerate}


\item%(b)

 \begin{enumerate}
 \item %1.
 ``Suppose we have a graph $G$ and a positive integer $k$.  Can we
 color the vertices of the graph with $k$ colors so that no edge has
 both its end points of the same color?''

 \item %2.
 This proof is almost the same as for (a)2, so I will abbreviate.

 Any $k$-coloring of a graph is also a $k'$-coloring, for any
 $k' \geq k$.  Thus, if the optimization problem is solvable in
 polynomial time, we can solve the decision problem in polynomial
 time, since there exists a $k$-coloring if and only if the minimal
 coloring uses $k$ or less colors.

 The other direction uses the same method as (a)2: binary search,
 starting with $1 \rdots \|V\|$ as the bounds for $k$, since any graph
 can be $\|V\|$-colored.

 \item %3.
 Given a coloring of the graph, we could trivially determine whether
 it uses $k$ colors; and we need only iterate over every edge in the
 graph, checking that the endpoints have different colors, to check
 whether the coloring is a $k$-coloring of the graph, in polynomial
 time.

 \end{enumerate}


\item%(c)

 \begin{enumerate}
 \item %1.
 ``Suppose we have a finite set $U$, and a weight $w(u)$ and a value
 $v(u)$ for each item $u \in U$, where $w(u)$ and $v(u)$ are positive
 integers.  Given a knapsack which can carry a maximum weight $B$ and
 a positive integer $k$, can we fit a set of items from set $U$ with
 total value greater than or equal to $k$ into the sack?''

 \item %2.
 If the optimization problem is solvable in polynomial time, then we
 can solve the decision problem in polynomial time, since there exists
 a valid set with value greater than or equal to $k$ if and only if
 the maximum-value valid set has value greater than or equal to $k$.

 And yet again, we can use binary search to convert an algorithm to
 solve the decision problem into an algorithm to solve the
 optimization problem.  This time, unlike the other times, using a
 binary search rather than a straight linear search is vital, because
 the search bounds for $k$ are $1 \rdots \sum_{u \in U} v(u)$, and the
 maximum value $\sum_{u \in U} v(u)$ is not polynomial in the size of
 the input, but rather exponential.  However, since we use a binary
 search, the run time will be polynomial in the size of the input.

 \item %3.
 Given a subset of the items, we can add up their weights and add up
 their values in linear time, and then compare the total weight
 against $B$ and the total value against $k$ to determine whether the
 subset satisfies the criteria.

 \end{enumerate}


\end{enumerate}
\newpage



\end{document}
