%  Final examination: solutions
%  Combinatorial Optimization, SUAMI, summer 2015
%  Brian Kell <bkell@cmu.edu>

\pdfpagewidth=8.5truein \pdfpageheight=11truein
\hsize=5.5truein \vsize=9truein
\pdfhorigin=1.5truein \pdfvorigin=1truein

% MetaPost stuff
\input supp-pdf
\def\fig#1{\convertMPtoPDF{#1}{1}{1}}
\def\midfig#1{{%
	\setbox0=\hbox{\fig{#1}}%
	\dimen0=0.5\ht0%
	\advance\dimen0 by-0.3\ht\strutbox
	\lower\dimen0\box0%
}}

% AMSFonts
\input amssym.tex

% rsfs script fonts
\font\tenscr=rsfs10    \font\sevenscr=rsfs7     \font\fivescr=rsfs5
\skewchar\tenscr='177  \skewchar\sevenscr='177  \skewchar\fivescr='177
\newfam\scrfam
\textfont\scrfam=\tenscr  \scriptfont\scrfam=\sevenscr
  \scriptscriptfont\scrfam=\fivescr
\def\scr{\fam\scrfam}

\font\titlefont=cmbx12  \font\smfont=cmr8  \font\transposefont=cmss8 at6pt

\newcount\pno \pno=0
\def\problem{\global\advance\pno by1%
	\medbreak\noindent{\llap{\bf\the\pno.\enspace}}\ignorespaces}
\def\solution{\medskip\noindent\llap{$\triangleright$\bf\phantom.\enspace}{\bf Solution.}\enspace\ignorespaces}

% Pilfered from an example on page 106 of the TeXbook
\def\qed{{\unskip\nobreak\hfil\penalty50
	\hskip1em\hbox{}\nobreak\hfil\hbox{\vrule\vbox to6pt{\hrule\hbox to5.2pt{\hss}\vfil\hrule}\vrule}
	\parfillskip=0pt \finalhyphendemerits=0 \par}}
\def\subqed{{\unskip\nobreak\hfil\penalty50
	\hskip1em\hbox{}\nobreak\hfil\raise2pt\hbox{\vrule height4pt width4pt depth0pt}
	\parfillskip=0pt \finalhyphendemerits=0 \par}}

\newdimen\pivotwidth  \newdimen\pivotdepth
\def\pivot#1{%
	\setbox0=\hbox{\vphantom/$#1$}
	\pivotdepth=\dp0
	\setbox0=\hbox{\vbox{\vskip1pt\hbox{\hskip2pt\box0\hskip2pt}\vskip1pt}}%
	\pivotwidth=\wd0  \advance\pivotwidth by0.8pt
	\lower\pivotdepth\hbox{\vbox{%
		\vskip-1.4pt
		\hrule width\pivotwidth height0.4pt depth0.0pt
		\hbox{%
			\vrule height\ht0 depth\dp0 width0.4pt
			\copy0
			\vrule height\ht0 depth\dp0 width0.4pt
		}%
		\hrule width\pivotwidth height0.4pt depth0.0pt
		\vskip-1.4pt
	}\hskip-2.4pt}%
}

\def\frac#1#2{{\textstyle{{#1}\over{#2}}}}
\def\R{{\mathord{\Bbb R}}}  \def\Q{{\mathord{\Bbb Q}}}
\def\Z{{\mathord{\Bbb Z}}}  \def\N{{\mathord{\Bbb N}}}
\def\transpose{{\raise0.5pt\hbox{\transposefont T}}}
\def\labs{\mathopen|}  \def\rabs{\mathclose|}  \def\abs#1{\labs#1\rabs}
\def\dom{\mathop{\rm dom}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\centerline{\titlefont Combinatorial Optimization}
\smallskip
\centerline{\bf Final examination: solutions}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem In the simplex tableau below, several variables are candidates to
become basic in the next basic feasible solution.
$$\vbox{\offinterlineskip
\halign{&\enspace\hfil\strut$#$\enspace\cr
x_1&x_2&x_3&s_1&s_2&s_3&s_4&z&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
-5&0&0&-2&0&0&-6&1&\omit\vrule&245\cr
\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit\vrule height2pt\cr
\noalign{\hrule}
\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit\vrule height2pt\cr
5&1&0&1&0&0&-3&0&\omit\vrule&40\cr
2&0&0&1/2&1&0&2&0&\omit\vrule&18\cr
1/2&0&0&-4/3&0&1&3&0&\omit\vrule&12\cr
1&0&1&2/3&0&0&1/2&0&\omit\vrule&24\cr}}$$
Which variable should be made basic in the next basic feasible solution if the
goal is

\smallskip

\item{(a)} for the new objective value to be~285? Why?

\smallskip

\item{(b)} for the next basic feasible solution to be degenerate? Why?

\smallskip

\item{(c)} to have $s_3=0$ in the next basic feasible solution? Why?

\smallskip

\item{(d)} to achieve the greatest increase in the objective value? Why?

\solution First we observe that the three variables that are candidates to
become basic in the next basic feasible solution are $x_1$,~$s_1$, and~$s_4$,
because these are the columns that have negative entries in the objective row.
In the $x_1$~column, the minimum test ratio is $40/5=8$, which occurs in the
first row of the body of the tableau, In the $s_1$~column, there is a tie for
the minimum test ratio: $18/(1/2)=36$ in the second row of the body of the
tableau, and $24/(2/3)=36$ in the fourth row. In the $s_4$~column, the minimum
test ratio is $12/3=4$ in the third row. For convenience, these possible pivot
locations are marked in the tableau below.
$$\vbox{\offinterlineskip
\halign{&\enspace\hfil\strut$#$\enspace\cr
x_1&x_2&x_3&s_1&s_2&s_3&s_4&z&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
-5&0&0&-2&0&0&-6&1&\omit\vrule&245\cr
\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit\vrule height2pt\cr
\noalign{\hrule}
\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit\vrule height2pt\cr
\pivot5&1&0&1&0&0&-3&0&\omit\vrule&40\cr
2&0&0&\pivot{1/2}&1&0&2&0&\omit\vrule&18\cr
1/2&0&0&-4/3&0&1&\pivot3&0&\omit\vrule&12\cr
1&0&1&\pivot{2/3}&0&0&1/2&0&\omit\vrule&24\cr}}$$

\item{(a)} If $x_1$ is chosen as the pivot column, then to make the entry in
the objective row zero, we must add the first row of the body of the (given)
tableau to the objective row. This will cause the objective value to increase
by~40 to~285, as desired. So $x_1$ should be made basic.

\medskip

\item{(b)} There is a tie for the minimum test ratio in the $s_1$~column, so
pivoting in this column will result in a zero in the RHS column (below the
objective value), which means the corresponding basic feasible solution is
degenerate. So $s_1$ should be made basic.

\medskip

\item{(c)} We can make $s_3=0$ by kicking it out of the basis. To do so, we
will need to pivot in the third row of the body of the tableau. This is
possible only if we pivot in the $s_4$~column, so $s_4$ should be made basic.

\medskip

\item{(d)} Pivoting in the $x_1$~column will increase the objective value
by~40, as we saw in part~(a). Pivoting in the $s_1$~column will increase the
objective value by~72. Pivoting in the $s_4$~column will increase the objective
value by~24. Therefore $s_1$~should be made basic. \qed

\vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Consider the following linear program.
$$\eqalign{
	{\rm minimize}\quad5y_1+3y_2+6y_3&\cr
	{\rm subject\ to}\quad\phantom1y_1\phantom{{}+0y_2}+\phantom1y_3&\ge60\cr
	y_1+2y_2+\phantom1y_3&\ge72\cr
	2y_1+\phantom1y_2+2y_3&\ge84\cr
	y_2-\phantom1y_3&\ge24\cr
	&\phantom{{}=00}\llap{$y_1\ge0$,\quad$y_2\ge0$,\quad$y_3\ge0$}.\cr
}$$
The optimal feasible solution to this linear program is $y_1=60$, $y_2=24$, and
$y_3=0$. Determine the dual linear program and its optimal solution. Use the
optimal dual solution to demonstrate that the claimed optimal solution to the
primal is indeed optimal.

\solution The dual of the given linear program is
$$\eqalign{
	{\rm maximize}\quad60x_1+72x_2+84x_3+24x_4&\cr
	{\rm subject\ to}\quad\phantom{01}x_1+\phantom{01}x_2+\phantom02x_3\phantom{{}+00x_4}&\le5\cr
	2x_2+\phantom{01}x_3+\phantom{01}x_4&\le3\cr
	x_1+\phantom{01}x_2+\phantom02x_3-\phantom{01}x_4&\le6\cr
	\hbox{$x_1\ge0$,\quad$x_2\ge0$,\quad$x_3\ge0$,\quad$x_4$}&\ge0.\cr
}$$

\noindent By complementary slackness applied to the primal variables and the
dual constraints:

\smallskip

\item{1.} Either $y_1=0$ (which is false) or $x_1+x_2+2x_3=5$.

\smallskip

\item{2.} Either $y_2=0$ (which is false) or $2x_2+x_3+x_4=3$.

\smallskip

\item{3.} Either $y_3=0$ (which is true) or $x_1+x_2+2x_3-x_4=6$.

\smallskip

\noindent Therefore we can deduce that the optimal dual solution must satisfy
the following system of equations.
$$\left\{\eqalign{
	x_1+\phantom1x_2+2x_3\phantom{{}+x_4}&=5\cr
	2x_2+\phantom1x_3+x_4&=3.\cr
}\right.\eqno(\star)$$

\noindent By complementary slackness applied to the dual variables and the
primal constraints:

\smallskip

\item{1.} Either $x_1=0$ or $y_1+y_3=60$ (which is true).

\smallskip

\item{2.} Either $x_2=0$ or $y_1+2y_2+y_3=72$ (which is false).

\smallskip

\item{3.} Either $x_3=0$ or $2y_1+y_2+2y_3=84$ (which is false).

\smallskip

\item{4.} Either $x_4=0$ or $y_2-y_3=24$ (which is true).

\smallskip

\noindent So we know that $x_2=0$ and $x_3=0$. Hence the system~$(\star)$ from
above becomes $x_1=5$, $x_4=3$, so the optimal dual solution is
$$x_1=5,\quad x_2=0,\quad x_3=0,\quad x_4=3.$$

\goodbreak

\noindent To demonstrate that the claimed optimal primal solution is indeed
optimal, we use the optimal dual solution as multipliers for the constraints in
the primal:
$$\eqalign{
	5\,(\phantom1y_1\phantom{{}+0y_2}+\phantom1y_3&\ge\phantom060)\cr
	0\,(\phantom1y_1+2y_2+\phantom1y_3&\ge\phantom072)\cr
	0\,(2y_1+\phantom1y_2+2y_3&\ge\phantom084)\cr
	{}+3\,(\phantom{0y_1+1}y_2-\phantom1y_3&\ge\phantom024)\cr
\noalign{\vskip2pt\hrule\vskip2pt}
	5y_1+3y_2+2y_3&\ge372.\cr
}$$
Because $y_1$,~$y_2$, and~$y_3$ are all nonnegative, we have
$$5y_1+3y_2+6y_3\ge5y_1+3y_2+2y_3\ge372,$$
so any feasible solution to the primal must have objective value at least~372.
It is easy to check that the given primal solution is feasible, and it has
objective value $5(60)+3(24)+6(0)=372$, so it is optimal. \qed

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Formulate a linear or integer program to answer the following
question.

{\medskip\narrower

\noindent A company manufactures three product lines. Each production run of
line~$i$ involves a fixed cost~$F_i$ and a per-unit cost~$p_i$, so that the
cost of $x_i$~units of line~$i$ is $F_i+p_ix_i$. These costs, together with the
per-unit revenue, are given in the table below.
$$\vbox{\offinterlineskip
\halign{\enspace\hfil\strut#\hfil\enspace&\vrule#&&\enspace\hfil\strut#\hfil\enspace\cr
Product&&Fixed&Per-unit&Per-unit\cr
line&&cost&cost&revenue\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
1&&\$1500&\$45&\$240\cr
2&&\phantom{\$0}900&\phantom\$38&\phantom\$190\cr
3&&\phantom\$1000&\phantom\$40&\phantom\$210\cr}}$$
There are two key production processes, A~and~B. The time requirements for
each product line on each process, and the hours available, are given in the
table below.
$$\vbox{\offinterlineskip
\halign{&\enspace\hfil\strut#\hfil\enspace&\vrule#&\enspace\hfil\strut#\hfil\enspace&\enspace\hfil\strut#\hfil\enspace\cr
&&\multispan3\enspace\hfil\strut Product line\hfil\enspace&&Hours\cr
Process&&1&2&3&&available\cr
\omit&height2pt&\omit&\omit&\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt&\omit&\omit&\omit&height2pt\cr
A&&0.25&0.20&0.30&&300\cr
B&&0.40&0.50&0.20&&400\cr}}$$
The company will upgrade exactly one of the two processes. The upgrade to
Process~A will raise the number of effective hours by~20\%; that to Process~B
will raise the number of effective hours by~10\%.

Which process should the company upgrade, and how much of each product line
should be manufactured in order to maximize the difference between revenue and
cost?

\par}

\solution For $i\in\{1,2,3\}$, let $x_i\ge0$ denote the number of units of
product line~$i$ to produce, and let $b_i\in\{0,1\}$ denote whether to pay the
fixed cost for line~$i$. Let $a\in\{0,1\}$ denote whether to upgrade Process~A.
(If $a=0$, then Process~B will be upgraded instead.) The objective is to
maximize the difference between revenue and cost:
$$\eqalignno{
	{\rm maximize}\quad&240x_1+190x_2+210x_3&\hbox{[revenue]}\cr
	&-1500b_1-900b_2-1000b_3&\hbox{[fixed cost]}\cr
	&-45x_1-38x_2-40x_3.&\hbox{[per-unit cost]}\cr
}$$
Equivalently,
$${\rm maximize}\quad195x_1+152x_2+170x_3-1500b_1-900b_2-1000b_3.$$

\noindent We have resource constraints for the available time on Processes
A~and~B. The number of available hours on Process~A is $300+30a$, because
upgrading Process~A gives us 30~additional hours, and the number of available
hours on Process~B is $400+40(1-a)$, because upgrading Process~B (indicated by
$a=0$) gives us 40~additional hours. So the resource constraints for the two
processes are
$$\eqalign{
	0.25x_1+0.20x_2+0.30x_3&\le300+60a,\cr
	0.40x_1+0.50x_2+0.20x_3&\le400+40(1-a).\cr
}$$
Furthermore, we cannot produce any units of a product line unless we pay the
corresponding fixed cost, so we have
$$\eqalign{
	x_1&\le1{,}000{,}000\,b_1,\cr
	x_2&\le1{,}000{,}000\,b_2,\cr
	x_3&\le1{,}000{,}000\,b_3.\cr
}$$
These constraints force $x_i=0$ when $b_i=0$. The coefficient 1,000,000 here
just needs to be large enough so that $x_i$ is not practically constrained when
$b_i=1$.

\goodbreak

\noindent So the complete IP formulation is
$$\displaylines{
	\openup-1\jot
	\eqalign{
		{\rm maximize}\quad&195x_1+152x_2+170x_3-1500b_1-900b_2-1000b_3\cr
		{\rm subject\ to}\quad&0.25x_1+0.20x_2+0.30x_3\le300+60a\cr
		&0.40x_1+0.50x_2+0.20x_3\le400+40(1-a)\cr
		&\phantom{0.00x_1+0.00x_2+1.00}x_1\le1{,}000{,}000\,b_1\cr
		&\phantom{0.00x_1+0.00x_2+1.00}x_2\le1{,}000{,}000\,b_2\cr
		&\phantom{0.00x_1+0.00x_2+1.00}x_3\le1{,}000{,}000\,b_3\cr
	}\cr
	\hfill\hbox{$x_1\ge0$,\quad$x_2\ge0$,\quad$x_3\ge0$,\quad$b_1\in\{0,1\}$,\quad
		$b_2\in\{0,1\}$,\quad$b_3\in\{0,1\}$,\quad$a\in\{0,1\}$}.\hfill\llap{\hbox{\qed}}\cr
}$$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem In the following network, capacities of arcs are shown as circled
numbers, and flows along arcs are shown in blue. Is the given $s$--$t$ flow
optimal? If so, prove that it is optimal. If not, find (methodically) a better
flow.
$$\fig{final-flow-1.mps}$$

\def\xout#1{\setbox0=\hbox{#1}\hbox to\wd0{\hss$\backslash$\hss}\llap{\box0}}

\solution The value of the given $s$--$t$ flow is~20. The result of one
iteration of the Ford--Fulkerson algorithm is shown in the figure at the top of
the next page. In this figure, the capacities of the arcs are shown circled in
gray, the node labels are in green, and nonzero flows along arcs are in light
blue. The node labels are given in the form $({\it from}[i],\hbox{\it
how-much}[i])$. Arcs with zero flow are drawn as straight black arrows,
saturated arcs are drawn as double red arrows, and unsaturated arcs with
nonzero flow are drawn as wavy light blue arrows. Below the figure is the
{\it LIST\/} of vertices built up as the Ford--Fulkerson algorithm progresses
through the network. We treat the {\it LIST\/} as a queue here: nodes are added
to the right-hand side when they are labeled, and they are removed from the
left-hand side (indicated by crossing them out) when they are scanned.

\vfill\eject

$$\displaylines{
	\fig{final-solns-ff.mps}\cr
	\hbox{{\it LIST\/}: \xout{$s$}; \xout{$a$}; \xout{$f$}; \xout{$d$};
		\xout{$b$}, \xout{$g$}; \xout{$e$}; \xout{$c$}, \xout{$h$}; $t$.}\cr
}$$

\noindent The node~$t$ received a label, which means that the current flow is
not optimal. By following the labels backward from~$t$, we discover the
augmenting path $s$--$a$--$f$--$d$--$b$--$e$--$h$--$t$. We augment the flow
along this path by~1, bearing in mind that the path traverses the arcs $(b,d)$
and $(e,b)$ in the backward direction, so augmenting the flow along the path
involves {\it decreasing\/} the flow on these arcs. This results in the
following flow.

$$\fig{final-solns-newflow.mps}$$
This new $s$--$t$ flow has value~21, which is better than the flow given in the
problem. \qed

\vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Constraint programming is an important area of combinatorial
optimization that we did not discuss in this course. An instance of a
constraint programming problem (in particular, a constraint satisfaction
problem) consists of a finite set~$X$ of variables; a finite set~$\dom(x)$ for
each variable~$x\in X$, called the {\it domain\/} of~$x$; and a set of
{\it constraints}, each of which specifies, directly or indirectly, a set of
allowable combinations of values for a subset of the variables. The objective
is to find an assignment of values to all of the variables such that for every
variable~$x\in X$ the value assigned to~$x$ is an element of~$\dom(x)$ and such
that all constraints are satisfied, or to determine that no such satisfying
assignment exists.

One type of constraint is the {\it alldiff\/} constraint, which specifies that
the values of a subset of the variables must all be different. For example, the
constraint ${\it alldiff\/}(x_1,x_3,x_4,x_8)$ means that the values assigned to
the variables $x_1$,~$x_3$, $x_4$, and~$x_8$ must all be different; no two of
those variables may be assigned the same value.

Suppose you are given an {\it alldiff\/} constraint and the domains of the
variables in the constraint. Carefully describe an efficient algorithm to
determine whether the {\it alldiff\/} constraint is satisfiable (alone,
independently of any other constraints that happen to be in the constraint
satisfaction problem). Justify that your algorithm is correct. You may use any
of the algorithms we discussed in the course as subroutines in your algorithm.

\solution Construct a bipartite graph $G=(U\cup V,E)$ where $U$ is the set of
variables in the given {\it alldiff\/} constraint and $V$~is the {\it union\/}
of the domains of these variables. Put an edge between a vertex~$x\in U$ (i.e.,
a variable~$x$) and a vertex~$v\in V$ (i.e., a value) if and only~if
$v\in\dom(x)$. Now find a maximum matching~$M$ in the bipartite graph~$G$,
using (for example) the augmenting-path algorithm or the network flow
formulation we discussed in class. If $\abs M=\abs U$, then return ``yes'';
otherwise, return ``no.''

Why is this algorithm correct? If $\abs M=\abs U$, then every
variable~$x\in U$ is matched by~$M$ to a value~$v_x\in V$. By the construction
of~$G$, we must have $v_x\in\dom(x)$ for all~$x\in U$. And because $M$ is a
matching, no two variables are matched to the same value. So the
{\it alldiff\/} constraint can be satisfied (in fact, $M$~gives a satisfying
assignment of values to the variables). On the other hand, if $\abs M<\abs U$,
then, because $M$ is a maximum matching in~$G$, it is impossible to match each
variable~$x\in U$ with a value~$v_x\in V$ such that $v_x\in\dom(x)$ for all~$x$
and the values~$v_x$ are all different, so the {\it alldiff\/} constraint
cannot be satisfied. \qed

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem In the {\smfont SET PACKING} problem, an instance is a
collection~$\scr C$ of finite sets and a positive integer~$k$, and the question
is whether $\scr C$ contains $k$~disjoint sets. Prove that {\smfont SET
PACKING} is NP-hard.

\solution To show that {\smfont SET PACKING} is NP-hard, it suffices to give a
polynomial-time transformation from a known NP-complete problem to {\smfont SET
PACKING}.

Here is a polynomial-time transformation from {\smfont INDEPENDENT SET} to
{\smfont SET PACKING}. Let $(G,k)$ be an instance of {\smfont INDEPENDENT SET},
where $G=(V,E)$ is a graph and $k$~is a positive integer. (The question in this
instance is whether $G$~contains an independent set of size~$k$.) For $v\in V$,
let $E_v=\{\,e\in E:v\in e\,\}$ be the set of edges incident upon~$v$.
Construct the instance~$({\scr C},k)$ of {\smfont SET PACKING}, where
${\scr C}=\bigl\{\,\{v\}\cup E_v:v\in V\,\bigr\}$ and $k$~is the same as in the
instance of {\smfont INDEPENDENT SET}.

For any $v\in V$, the set~$E_v$ can be determined in $O(\abs E)$~time, so
$\scr C$~can be constructed in $O(\abs V\cdot\abs E)$~time, which is polynomial
in the size of the instance~$(G,k)$.

Now we show that $({\scr C},k)$ is a ``yes'' instance of {\smfont SET PACKING}
if and only~if $(G,k)$~is a ``yes'' instance of {\smfont INDEPENDENT SET}.

Suppose $({\scr C},k)$ is a ``yes'' instance of {\smfont SET PACKING}. Then
$\scr C$ contains $k$~disjoint sets of the form $\{v_1\}\cup E_{v_1}$,
$\{v_2\}\cup E_{v_2}$, \dots, $\{v_k\}\cup E_{v_k}$. Because these sets are
disjoint, for $i\not=j$ no edge is in both $E_{v_i}$~and~$E_{v_j}$, which is to
say that no edge is incident upon both $v_i$~and~$v_j$, so $v_i$~and~$v_j$ are
not adjacent. Therefore $\{v_1,v_2,\ldots,v_k\}$ is an independent set of
size~$k$ in~$G$, so $(G,k)$ is a ``yes'' instance of {\smfont INDEPENDENT SET}.

Conversely, suppose $(G,k)$ is a ``yes'' instance of {\smfont INDEPENDENT SET}.
Then $G$ contains an independent set $\{v_1,v_2,\ldots,v_k\}$ of size~$k$. The
corresponding sets $\{v_1\}\cup E_{v_1}$, $\{v_2\}\cup E_{v_2}$, \dots,
$\{v_k\}\cup E_{v_k}$ in~$\scr C$ must be disjoint, because for $i\not=j$
plainly $v_i\not=v_j$ and also $E_{v_i}\cap E_{v_j}=\emptyset$ because no edge
is incident upon both $v_i$~and~$v_j$. Moreover $\{v_i\}\cup E_{v_i}$ and
$\{v_j\}\cup E_{v_j}$ are distinct, because the first set contains~$v_i$ but
the second does not. So these are $k$~disjoint sets in~$\scr C$, which means
$({\scr C},k)$ is a ``yes'' instance of {\smfont SET PACKING}.

We showed in class that {\smfont INDEPENDENT SET} is NP-complete, so this
polynomial-time transformation from {\smfont INDEPENDENT SET} to
{\smfont SET PACKING} establishes that {\smfont SET PACKING} is NP-hard. \qed

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bye
