%\documentstyle[10pt,twoside]{article}
\documentstyle[twoside, 11pt]{article}
\setlength{\oddsidemargin}{0.25 in}
\setlength{\evensidemargin}{-0.25 in}
\setlength{\topmargin}{-0.6 in}
\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\headsep}{0.75 in}
\setlength{\parindent}{0 in}
\setlength{\parskip}{0.1 in}
%
% The following commands sets up the lecnum (lecture number)
% counter and make various numbering schemes work relative
% to the lecture number.
%
\newcounter{lecnum}
\renewcommand{\thepage}{\thelecnum-\arabic{page}}
\renewcommand{\thesection}{\thelecnum.\arabic{section}}
\renewcommand{\theequation}{\thelecnum.\arabic{equation}}
\renewcommand{\thefigure}{\thelecnum.\arabic{figure}}
\renewcommand{\thetable}{\thelecnum.\arabic{table}}
%
% The following macro is used to generate the header.
%
\newcommand{\problemset}[3]{
\pagestyle{myheadings}
\thispagestyle{plain}
\newpage
\setcounter{lecnum}{#1}
\setcounter{page}{1}
\noindent
\begin{center}
\framebox{
\vbox{\vspace{2mm}
\hbox to 6.28in { {\bf CS~21~~~Decidability and Tractability
\hfill Winter 2019} }
\vspace{4mm}
\hbox to 6.28in { {\Large \hfill Problem Set #1 \hfill} }
\vspace{2mm}
\hbox to 6.28in { {\it Out: #2 \hfill Due: #3} }
\vspace{2mm}}
}
\end{center}
\vspace*{4mm}
}
%
% Convention for citations is authors' initials followed by the year.
% For example, to cite a paper by Leighton and Maggs you would type
% \cite{LM89}, and to cite a paper by Strassen you would type \cite{S69}.
% (To avoid bibliography problems, for now we redefine the \cite command.)
%
\renewcommand{\cite}[1]{[#1]}
\input{epsf}
%Use this command for a figure; it puts a figure in wherever you want it.
%usage: \fig{NUMBER}{FIGURE-SIZE}{CAPTION}{FILENAME}
\newcommand{\fig}[4]{
\vspace{0.2 in}
\setlength{\epsfxsize}{#2}
\centerline{\epsfbox{#4}}
\begin{center}
Figure \thelecnum.#1:~#3
\end{center}
}
% Use these for theorems, lemmas, proofs, etc.
\newtheorem{theorem}{Theorem}[lecnum]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newenvironment{proof}{{\bf Proof:}}{\hfill\rule{2mm}{2mm}}
% Some useful equation alignment commands, borrowed from TeX
\makeatletter
\def\eqalign#1{\,\vcenter{\openup\jot\m@th
\ialign{\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
\crcr#1\crcr}}\,}
\def\eqalignno#1{\displ@y \tabskip\@centering
\halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
&$\displaystyle{{}##}$\hfil\tabskip\@centering
&\llap{$##$}\tabskip\z@skip\crcr
#1\crcr}}
\def\leqalignno#1{\displ@y \tabskip\@centering
\halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
&$\displaystyle{{}##}$\hfil\tabskip\@centering
&\kern-\displaywidth\rlap{$##$}\tabskip\displaywidth\crcr
#1\crcr}}
\makeatother
% **** IF YOU WANT TO DEFINE ADDITIONAL MACROS FOR YOURSELF, PUT THEM HERE:
\begin{document}
\problemset{6}{February 27}{\bf {March 6}}
Reminder: you are encouraged to work in groups of two or three;
however you must turn in your own write-up and note with whom you
worked. You may consult the course notes and the text (Sipser). The
full honor code guidelines and collaboration policy can be found in the course syllabus.
Please attempt all problems. {\bf Please turn in your solutions via
Gradescope, by 1pm on the due date.}
\begin{enumerate}
\item Recall that two graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2,
E_2)$ are {\em isomorphic} if there is a bijection $f:V_1
\rightarrow V_2$ such that $(u, v) \in E_1 \Leftrightarrow (f(u),
f(v)) \in E_2$. On the Problem Set 4 you showed that
${\mbox{\sc contains}}_H$ is in P.
Prove that the following variation in which $H$ is part of the
input is NP-complete:
\[\mbox{{\sc subgraph isomorphism}} = \{(G, H) : \mbox{$G$
contains a subgraph isomorphic to $H$}\}.\] As in the previous
problem set, by ``subgraph'' we mean a subset of $G$'s vertices
together with all of $G$'s edges on that subset of vertices. A
side note: the related problem \[\mbox{{\sc graph isomorphism}} =
\{(G, H) : \mbox{$G$ is isomorphic to $H$}\}\] is not know to be
NP-complete, nor is it known to be in P.
\item Let ${\cal C} =
\{S_1, S_2, S_3, \ldots, S_n\}$ be a collection of sets and define $U = \cup_i S_i$. We
say that $T \subseteq {\cal C}$ is a {\em cover} if every
$u \in U$ occurs in at least one $S_i \in T$. Prove that the language:
\[\mbox{\sc set cover} = \{({\cal C}, k) : \mbox{there is a cover $T \subseteq {\cal C}$ with $|T| \le k$}\}.\]
is NP-complete.
\item A {\em bisection} of a graph $G = (V,E)$ is a cut $S
\subseteq V$ with $|S| = |V|/2$. A powerful and general
algorithmic strategy is to represent the ``components'' of a
problem by vertices of a graph $G$ and dependencies between
components by its edges; then a bisection splits the problem into
two equal pieces, which can be solved recursively and merged to
produce a global solution. In this general framework, the work in
the merging step often depends on the number of edges crossing the
bisection. Thus, one might hope to be able to efficiently solve
the following problem, {\sc minimum bisection}:
\[\{(G, k): \mbox{$G$ is a connected multigraph having a bisection with at most $k$ edges crossing it.}\}\]
Unfortunately, an efficient solution is unlikely. Prove that {\sc
min bisection} is NP-complete.
Hint: what is the relationship between this problem and the
maximization version, {\sc maximum bisection}: \[\{(G, k):
\mbox{$G$ is a connected multigraph having a bisection with at least $k$ edges crossing it.}\}?\]
\item
\begin{enumerate}
\item A list of positive integers $(a_1, a_2, \ldots, a_n)$
is {\em partitionable} if there is a subset $T \subseteq \{1,2,\ldots, n\}$ for
which $\sum_{i \in T} a_i = \sum_{i \not\in T} a_i.$ Show that the
following language is NP-complete:
\[\mbox{{\sc partition}} = \{S = (a_1, a_2, \ldots, a_n) : S \mbox{ is partitionable} \}\]
\item In the ``knapsack problem'' we are given $n$ items each of
which has a positive integer {\em cost} $c_i$ and a positive
integer {\em value} $v_i$. We are asked to pack a knapsack with
items whose total value is at least $V$, and without exceeding a
budget $C$. Show that the following language is NP-complete:
\begin{eqnarray*}
\mbox{{\sc knapsack}} & = & \{(c_1, c_2, \ldots, c_n,v_1, v_2,
\ldots,
v_n, V,C) : \exists \;T \subseteq \{1, 2, \ldots, n\}\\
& & \mbox{ for which } \sum_{t \in T}v_t \ge V \mbox{ and }
\sum_{t \in T}c_t \le C\}
\end{eqnarray*}
\end{enumerate}
\end{enumerate}
\end{document}