
%\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 2024} }
       \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 21}{\bf {February 28}}


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. Please select {\em one} the first two
problems to be graded completely (and indicate clearly which one); the other one
will receive 1 point for a credible attempt. {\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 cut} of an undirected graph $G = (V, E)$ is a subset of vertices $S
  \subseteq V$. We say that an edge  {\em crosses the cut} if one
  endpoint is in $S$ and the other is in $V \setminus S$. In class, we
  will show that the following language is NP-complete:
  \[{\sc maxcut} = \{(G=(V,E), k): \mbox{ there is a cut $S \subseteq V$
      with at least $k$ edges crossing it}.\]
In this problem you will consider a related problem concerning
 special cuts called bisections. 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 In class we will show that the following problem concerning
  positive integers is NP-complete:
  \[{\sc subset-sum}=\left \{(a_1, a_2, \ldots, a_n, B): \exists S
    \subseteq [n] \mbox{ for which }  \sum_{i \in S}a_i = B.\right \}\]

This will be useful when giving reductions for the following problems:
\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}
