\documentclass[11pt]{article}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{algorithm}
\usepackage{fullpage}
%\usepackage[]{algorithm2e}
\usepackage[normalem]{ulem}
\usepackage{xcolor}
\usepackage{tcolorbox}
\usepackage{latexsym}              % Additional LaTeX Symbols
\usepackage{amssymb}               % AMS Fonts
\usepackage[shortlabels]{enumitem}
\usepackage{pseudocode}
\newcommand{\nats}{\ensuremath{\mathbb N}}
\newcommand{\Real}{\ensuremath{\mathbb R}}
\newcommand{\ind}[1]{\hspace*{#1em}}
\newcommand{\Algorithm}{{\bf Algorithm\ }}
\newcommand{\Subroutine}{{\bf Subroutine\ }}
\newcommand{\Comment}{{\bf Comment\ }}
\newcommand{\Note}{{\bf Note:\ }}
\newcommand{\Assert}{{\bf assert:\ }}
\newcommand{\Input}{{\bf Input:\ }}
\newcommand{\Output}{{\bf Output:\ }}
\newcommand{\Caveat}{{\bf Caveat:\ }}
\newcommand{\Condition}{{\bf Condition:\ }}
\newcommand{\For}{{\bf for\ }}
\newcommand{\From}{{\bf from\ }}
\newcommand{\Downto}{{\bf downto\ }}
\newcommand{\To}{{\bf to\ }}
\newcommand{\By}{{\bf by\ }}
\newcommand{\Do}{{\bf do\ }}
\newcommand{\Od}{{\bf od}}
\newcommand{\While}{{\bf while\ }}
\newcommand{\If}{{\bf if\ }}
\newcommand{\Then}{{\bf then\ }}
\newcommand{\Else}{{\bf else\ }}
\newcommand{\Elif}{{\bf elif\ }}
\newcommand{\Fi}{{\bf fi}}
\newcommand{\myAnd}{{\bf and\ }}
\newcommand{\Or}{{\bf or\ }}
\newcommand{\Break}{{\bf break}}
\newcommand{\Next}{{\bf next}}
\newcommand{\Return}{{\bf return\ }}
\newcommand{\bigO}{{O\tilde{\phantom{\imath}}}}
\newcommand{\Z}{\ensuremath{\mathbb Z}}
\newcommand{\Q}{\ensuremath{\mathbb Q\mskip1mu}}
\newcommand{\K}{{\mathsf{K}}}
\newcommand{\F}{{\mathsf{F}}}
\newcommand{\R}{{\mathsf{R}}}
\newcommand{\B}{{\mathsf{B}}}
\newcommand{\M}{{\mathsf{M}}}
\newcommand{\MM}{{\mathsf{MM}}}
\newcommand{\remove}[1]{{}}
\newcommand{\ignore}[1]{{}}
\newcommand{\rednote}[1]{{\color{red} #1}}
\newcommand{\bluenote}[1]{{\color{blue} #1}}
\newcommand{\overbar}[1]{\mkern 1.5mu\overline{\mkern-1.5mu#1\mkern-1.5mu}\mkern 1.5mu}

\newif\ifmarking
\markingfalse

\newcommand{\markscheme}[1]{\ifmarking{\tcbset{colframe=red,colback=white,colupper=red}
\begin{tcolorbox}[size=small,arc=0mm]#1\end{tcolorbox}}\fi}

\newif\ifsoln
\solnfalse

\newcommand{\solution}[1]{\ifsoln{\tcbset{colframe=blue,colback=white,colupper=blue}
\begin{tcolorbox}[size=small,arc=0mm]#1\end{tcolorbox}}\fi}


% for typesetting code
\definecolor{commentsColor}{rgb}{0.497495, 0.497587, 0.497464}
\definecolor{keywordsColor}{rgb}{0.000000, 0.000000, 0.635294}
\definecolor{stringColor}{rgb}{0.558215, 0.000000, 0.135316}

\usepackage{xcolor}
\definecolor{stringColor}{rgb}{0.497495, 0.497587, 0.497464}
\definecolor{keywordsColor}{rgb}{0.000000, 0.000000, 0.635294}
\definecolor{commentsColor}{rgb}{0.558215, 0.000000, 0.135316}

\usepackage{listings}
\usepackage{hyperref}
\lstset{
  language=C++,
  columns=fullflexible,
  basicstyle=\ttfamily,
  commentstyle=\mycommentstyle,
  breaklines=true,
  escapechar=\$,
  rulecolor = \color{gray},
  frame=none,
  keywordstyle=\color{blue},
  stringstyle=\color{stringColor},
  commentstyle=\color{commentsColor}\textit,
  numbers = none,
  xleftmargin=0.5in
}
\hypersetup{
  colorlinks,
  linkcolor=blue,
}

\begin{document}

\noindent
{CS 341, Fall 2025 \hfill  T. Brown, É. Schost}

\begin{center}
\ifsoln{\large\bf ASSIGNMENT 5 SOLUTIONS}
\else{\large\bf ASSIGNMENT 5}
\fi
\end{center}

\ifsoln{\noindent\bf 
These solutions are for students currently enrolled in the Fall 2025 offering of CS 341 only.  You may not share or distribute them with anyone outside the course without explicit written permission from the instructors. (To do so is a violation of academic conduct.)}
\fi

\bigskip
\noindent
DUE: Tue Dec 2, 11:59 PM.
DO NOT COPY.  ACKNOWLEDGE YOUR SOURCES.

\medskip
\noindent
Please read \verb|http://www.student.cs.uwaterloo.ca/~cs341| for
general instructions and policies.


{\bf Note:} All logarithms default to base 2 (i.e.,  $\log x$ is defined as $\log_2 x$).
{\bf Note:}  ``Giving'' an algorithm means doing the four parts (i)--(iv) as described on the course web page. \textbf{Proofs are required unless we explicitly state otherwise.} If you think we made a mistake and a proof is not required, feel free to ask. %This goes without saying for all future assignments and exams.
You may use the \textbf{unit cost model unless otherwise stated}.

\bigskip
\noindent



\begin{enumerate}

\item{[10 marks]} (6 marks, 2 marks, 2 marks)
In the {\sc Clique3} problem, we are given a graph $G = (V,E)$ with maximum degree $3$ and a positive integer $k$; we must determine if $G$ has a clique of size at least $k$ or not. (A clique is a (sub)set of the graph's vertices that have all-to-all edges. That is, the subgraph defined by these vertices is a \textit{complete} graph.)

\begin{enumerate}[(i)]

\item Prove that $\textsc{Clique3} \in {\bf NP}$.

\item Here's a claimed proof that \textsc{Clique3} is {\bf NP}-complete. Explain why the argument is incorrect.

\begin{quote}
We showed in part (a) that {\sc Clique3} is in {\bf NP}.

We (will) know from lectures that {\sc Clique} is {\bf NP}-complete.  

We complete the proof by showing that $\textsc{Clique3} \le_{\bf P} \textsc{Clique}$: Let $F$ be the (trivial) algorithm that takes in a graph G with vertices of degree at most 3 and a parameter $k$, and leaves both as-is. The algorithm $F$  runs in polynomial time and gives a transformation from inputs of the {\sc Clique3} problem to inputs of the {\sc Clique} problem, and the answer to these inputs is always identical. Therefore, this is a valid polynomial-time reduction and {\sc Clique3} is {\bf NP}-complete.
\end{quote}


\item 
In the {\sc VertexCover3} problem, we are given a graph $G = (V,E)$ with maximum degree $3$ and a positive integer $k$; we must determine if $G$ has a vertex cover of size at most $k$ or not. It is known that {\sc VertexCover3} is {\bf NP}-complete, and for this question we may use this fact without proof.

Here's another claimed proof that \textsc{Clique3} is {\bf NP}-complete. Explain why the argument is incorrect.

\begin{quote}
We already showed in part (a) that {\sc Clique3} is in {\bf NP}. 

As stated in the question, we know that {\sc VertexCover3} is {\bf NP}-complete.

We complete the proof by showing that $\textsc{VertexCover3} \le_{\bf P} \textsc{Clique3}$: Let $F$ be the algorithm that transforms the input $(G,k)$ into the input $(\overline{G},n-k)$ where $\overline{G}$ is the complement of $G$---the graph on the same set $V$ of vertices as $G$ where for every pair of distinct vertices $u,v \in V$, $(u,v)$ is an edge in $\overline{G}$ if and only if it is not an edge in $G$.

The algorithm $F$ has polynomial-time complexity.
And there is a vertex cover of size $\le k$ in $G$ if and only if there is a clique of size at least $(n-k)$ in $\overline{G}$.
Therefore this is a valid polynomial-time reduction and {\sc Clique3} is NP-complete.
\end{quote}

\end{enumerate}

\item{[10 marks]} Minimum S-spanning tree.

Suppose we take as input an undirected graph $G=(V,E)$ with $n$ nodes and $m$ edges, and a non-negative weight function $w$ such that $w(e)$ is the weight of edge $e$, as well as a set $S \subseteq V$ of \textbf{important nodes}.
We want to connect all of the important nodes in $S \subseteq V$ together with the lowest total cost (i.e., lowest total sum of weights).

At first glance this might sound like the minimum spanning tree problem, but note that we do not have to connect \textit{all} nodes, but rather only the nodes in $S$.
That said, it may be cheaper to connect nodes in $S$ by using some nodes that are \textbf{not} in $S$.

As a trivial example, if we have three nodes $a, b, c$ and edges $(a,b,1), (b,c,1), (a,c,10)$, and $S = \{a,c\}$, we could connect the important nodes $a$ and $c$ with a single edge at cost 10, or with two edges via a non-important node $b$ at cost 2.
The latter is, of course, better, even though we have also connected a non-important node.

We can define two flavours of this problem: a \textbf{decision} version, and an \textbf{optimization} version.

Decision version (\textsc{MSST-Dec}): In addition to the basic input above, the input also includes a threshold $k$.
The desired output is: true if there is a way to connect all nodes in $S$ with total cost $\le k$, and false otherwise.

Optimization version (\textsc{MSST-Opt}): The input is just the basic input above (\textbf{no} threshold $k$).
The desired output is a \textbf{list of edges} that connect all nodes in $S$ with the lowest total cost.
If there is no way to connect them, you can return $\infty$.

The goal in this question is to find a \textbf{polynomial Turing reduction} from the optimization version to the decision version.
In other words, you are to prove $\textsc{MSST-Opt} \le_P^T \textsc{MSST-Dec}$.

(To be clear, this involves ``giving'' an algorithm.
So, you'll want to prove correctness, i.e., that your reduction always returns the \textit{correct} value.
And you'll want to compute your runtime, input size, and show the runtime is polynomial in the input size.
Unit cost model is fine.)


\item{[25 marks]} {\em NP-Completeness} Consider the {\textsc SINK-SOURCE SUBGRAPH (SSS)} problem:

Input: a directed graph $G(V, E)$.

Output: ``YES'' iff there is a subgraph $H(V,E')$, with $E' \subseteq E$, such that each $v \in V$ satisfies one of two conditions: (i) either, in-degree($v$) = 0 and out-degree($v$) $>$ 0; or (ii) out-degree($v$) = 0 and in-degree($v$) $>$ 0. The in/out degree conditions are within $H$.\footnote{In other words, an edge from a node $u \in H$ to a node $v \notin H$ does \textbf{not} count towards out-degree($u$), and an edge from $v$ to $u$ does \textbf{not} count towards in-degree($u$).}

\xdef\tpd{\the\prevdepth}
\vspace{5pt}

Let us call a subgraph $H$ satisfying the above property {\em sink-source} subgraph. Observe that in a sink-source subgraph, there are no paths of length 2, since every vertex either has zero in-degree or zero out-degree.

\begin{enumerate}
\item{[5 marks]} Prove that \textsc{SSS} is in NP.

\item{[20 marks]} Prove that \textsc{SSS} is NP-Complete through a reduction from \textsc{3SAT}. Remember to have an iff argument in your reduction.

[Hint: Consider having one vertex $u_i$ for each clause $C_i$ in the \textsc{3SAT} formula. Similarly have one vertex $v_j$ for each variable $x_j$ in the \textsc{3SAT} formula. If $x_j$ appears in $C_i$ have an edge from $v_j$ to $u_i$. If $\overbar{x_j}$ appears in $C_i$, add another edge from $u_i$ to $v_j$. Add another vertex $t$ to the graph and add edges from each $v_j$ to $t$. Finally, add one more node $s$ and add an edge from $s$ to $t$.]

\end{enumerate}

\end{enumerate}

\end{document}
