\documentclass[answers]{exam}
 
 \usepackage{graphicx}
 \usepackage{float}
 \usepackage{amsmath}
 \usepackage{mdframed}
% \usepackage{xcolor}
 \usepackage[dvipsnames]{xcolor}

 
 
\newcommand{\NP}{\mathsf{NP}}
\newcommand{\p}{\mathsf{P}}
 
% First, we setup the header and footer
\pagestyle{headandfoot}
\runningheadrule
\runningfootrule
\header{COL758: Advanced Algorithms (CSE, IITD, Semester-II-2022-23)}{}{Homework-1}
\footer{}{\thepage  \, of \numpages}{}
 
% We want the points for each question displayed on the left
%\pointname{points}
%\pointsinmargin
 
% Automatically total the points - make sure to compile TWICE
\addpoints
 
\begin{document}
 
\begin{center} 
\fbox{\parbox{5.5in}{
\vspace{-0.1in}
\begin{itemize}
\item \small{Homework solutions should be neatly written or typed and turned in through {\bf Gradescope} by 11:59 pm on the due date. No late homework will be accepted for any reason.  You will be able to look at your scanned work before submitting it. Please ensure that your submission is legible (neatly written and not too faint), or your homework may not be graded.}

\item \small{Students should consult their textbook, class notes, lecture slides, instructor, and TAs when they need help with homework. Students should not look for answers to homework problems in other texts or sources, including the internet. Only post about graded homework questions on Piazza if you suspect a typo in the assignment or if you don't understand what the question is asking you to do.}

\item \small{Your assignments in this class will be evaluated not only on the correctness of your answers but on your ability to present your ideas clearly and logically. You should always explain how you arrived at your conclusions using mathematically sound reasoning. Whether you use formal proof techniques or write a more informal argument for why something is true, your answers should always be well-supported. Your goal should be to convince the reader that your results and methods are sound.}

\item \small{For questions requiring pseudocode, you can follow the same format as we do in class or write pseudocode in your style, as long as you specify your notation. For example, are you using ``='' to mean assignment or to check equality? You are welcome to use any algorithm from class as a subroutine in your pseudocode. For example, if you want to sort list $A$ using {\tt InsertionSort}, you can call {\tt InsertionSort($A$)} instead of writing out the pseudocode for {\tt InsertionSort}.}

\item \small{You may use any of the following known $\mathsf{NP}$-complete problems to show that a given problem is $\mathsf{NP}$-complete: 3-SAT, INDEPENDENT-SET, VERTEX-COVER, SET-COVER, HAMILTONIAN- CYCLE, HAMILTONIAN-PATH, SUBSET-SUM, 3-COLORING.}
\end{itemize}
\vspace{-0.1in}
}}
\end{center}

\vspace{0.1in}


\vspace{0.1in}
% Some general text together with several questions and total points possible
There are \numquestions\, questions for a total of \numpoints\, points.
\vspace{0.1in}
\hrule
 \vspace{0.2in}
\begin{questions}
 
% First question, worth 3 points
\question Show that the following problems that were discussed in class are $\mathsf{NP}$-hard:
\begin{parts}
\part[10] Minimum makespan
\part[10] Dominating set
\end{parts}





\vspace{0.1in}


\question[20] Consider the following problem:
\begin{quote}
SPAN-TREE: Given an undirected graph $G = (V, E)$, determine if there is a spanning tree of $G$ that has at most $10$ leaves. 
\end{quote}
Either show that SPAN-TREE is $\mathsf{NP}$-complete or give a polynomial time algorithm (along with correctness proof and running time discussion).


\begin{solution}
WRITE YOUR SOLUTION HERE.
\end{solution}


\vspace{0.1in}


\question[20] Consider the following problem: 
\begin{quote}
F-SAT: Given a boolean formula in CNF form such that (i) each clause has exactly $3$ terms and (ii) each variable appears in at most $3$ clauses (including in negated form), determine if the formula is satisfiable.
\end{quote}
Answer the following questions with respect to the above problem under the assumptions (i)  $\p = \NP$, and (ii) $\p \neq \NP$. Give reasons.
\begin{enumerate}
\item[(a)] Is F-SAT $\in$ $\NP$?

\item[(b)] Is F-SAT $\NP$-complete?

\item[(c)] Is F-SAT $\NP$-hard?

\item[(d)] Is F-SAT $\in$ $\p$?
\end{enumerate}






\vspace{0.1in}




\question[20] Consider the following problem:
\begin{quote}
LONG-PATH: Given a weighted, directed graph $G = (V,E)$, two vertices $s,t \in V$ and a number $W$, determine if there is a simple path between $s$ and $t$ such that the sum of weights of edges in this path is $\geq W$.
\end{quote}

Recall that a simple path is a path that does not have any vertices repeated. 
Either show that LONG-PATH is $\mathsf{NP}$-complete or give a polynomial time algorithm (along with correctness proof and running time discussion).





%\vspace{0.1in}






%\question[10] Recall the discussion of the shortest path problem in your algorithms course. There were issues related to negative edges. For example, while discussing Dijkstra's, we assumed that the given graph does not have negative edges since Dijkstra's does not work in the presence of negative edges. 
%Note that the shortest path problem does not make sense if the graph has negative cycles since shortest paths are not constrained to be simple paths.
%There are algorithms (such as Bellman-Ford) that detect a negative cycle if there exists one and, otherwise, give the shortest paths. Suppose we consider the following version of the shortest path problem, which is well-defined: 
%\begin{quote}
%{\em Given a directed, weighted graph (with possibly negative edges) and a node $s$, find the shortest \textcolor{BrickRed}{simple} paths from $s$ to all nodes in the graph.}
%\end{quote}

%Argue that the above problem is $\NP$-hard.


%\question[10] Show that the DOM-SET problem ({\em discussed in the class}) defined below, is $\mathsf{NP}$-hard.
%\begin{quote}
%DOM-SET: Given a graph $G = (V, E)$ and a positive integer $k$, determine if there is a dominating set of size at most $k$.
%\end{quote}
%A subset of nodes is said to be a {\em dominating set} in the graph $G = (V, E)$ if for every node $v \in V$, either $v$  or one of its neighbours is in the subset.




\vspace{0.1in}





%\question[15] Consider the following graph problem:
%\begin{quote}
%NEIGHBOUR-COVER: Given a graph $G = (V, E)$ and a positive integer $k$, determine if there is a subset of nodes $S$ of size at most $k$ that ``{\em neighbour-covers}" all the nodes. 
%\end{quote}
%A subset of nodes is said to {\em neighbour-cover} all the nodes in the graph $G = (V, E)$ if for every node $v \in V$, either $v$  or one of its neighbours is in the subset.

%Either show that NEIGHBOUR-COVER is $\mathsf{NP}$-complete or give a polynomial time algorithm (along with correctness proof and running time discussion).



%\vspace{0.1in}



%\question In this question, we consider the Metric $k$-center problem discussed in class. Show that:
%\begin{parts} 
%\part[10] The Metric $k$-center problem is $\NP$-hard.
%\part[10] There cannot exist a polynomial time approximation algorithm with an approximation guarantee better than $2$ unless $\p = \NP$.
%\end{parts}





%\vspace{0.1in}




\question Recall the Minimum Makespan problem discussed in class. 
We saw a greedy approximation algorithm and showed an approximation guarantee of $2-\frac{1}{m}$. Consider the following slightly modified algorithm:

\begin{framed}
{\tt GreedySortMakespan}

\hspace{0.1in} - Consider  jobs in decreasing order of duration

\hspace{0.1in} - While all jobs are not assigned 

\hspace{0.3in} - Assign the next job (as per the order defined) to a machine with the least load
\end{framed}

Let $OPT$ denote the value of an optimal solution, and $G$ be the value of the above greedy solution. Then we will argue that $G \leq (4/3) \cdot OPT$. WLOG, let us assume that $d(1) \geq d(2) \geq ... \geq d(n)$. 

Let us call a problem instance $(d(1), ..., d(n))$ {\em nice} if as per the above greedy algorithm, the job with the maximum finishing time is $n$.
We will first argue that it is sufficient to analyze the approximation guarantee for nice instances.

\underline{Claim 1.1}: If our greedy algorithm gives a factor $c$ approximation for nice instances, then it gives factor $c$ approximation for all instances.

We can now focus on only nice instances. Again, for any nice instance, we use $G$ to denote the value of the greedy solution and $OPT$ to denote the value of an optimal solution.
Let us break the analysis into two cases: (i) $d(n) \leq OPT/3$, and (ii) $d(n) > OPT/3$. For case (i), we can make the following claim:

\underline{Claim 1.2}: If $d(n) \leq OPT/3$, then $G \leq (4/3) \cdot OPT$.

Now, consider the case when $d(n) > OPT/3$. We first show that $n \leq 2m$.

\underline{Claim 1.3}: If $d(n) > OPT/3$, then $n \leq 2m$.

Once we realize the above, the next thing we show is that, in this case, the greedy algorithm gives an optimal solution.

\underline{Claim 1.4} If $d(n) > OPT/3$, then {\tt GreedySortMakespan} returns an optimal solution.

Combining all the above claims, we get that the above greedy algorithm gives an approximation guarantee of $(4/3)$.

For this question, you have to answer the following:
\begin{parts}
\part[5] Prove Claim 1.1
\part[4] Prove Claim 1.2
\part[1] Prove Claim 1.3
\part[10] Prove Claim 1.4
\end{parts}


\end{questions}
\end{document}