\documentclass[11pt, a4paper, notitlepage, onecolumn, oneside, openany]{article}

\input{packages}
\input{layout}
\input{common_math}
\input{theorem_names_en}

\setlist[enumerate]{label={(\alph*)}, ref={(\alph*)}}
\setlist[description]{labelindent={2em}}


% Number algorithms under problems
\makeatletter
\renewcommand\thealgocf{%
  \theproblem.\arabic{algocf}}
\@addtoreset{algocf}{problem}
\makeatother


\title{%
  CMSC~28100-1 / MATH~28100-1\\
  Introduction to Complexity Theory\\
  Fall~2017 -- Homework~2\\
  Solution
}
\author{\relax}
\date{\today}

\begin{document}
\maketitle

\begin{exercise}
  The \emph{Knapsack Problem} is defined as follows. The input is a set~$S$ of~$\lvert S\rvert = n$ items,
  each with a positive integer weight~$w_i$ and a non-negative value~$v_i$ ($i\in S$), a positive integer knapsack
  capacity~$W$, and a positive integer target total value~$V$. The output should be ``Yes'' if there is a
  subset~$S'\subseteq S$ of items such that~$\sum_{i\in S'}w_i\leq W$ and~$\sum_{i\in S'} v_i\geq V$ and
  should be ``No'' otherwise.

  \begin{enumerate}
  \item Give an algorithm for the Knapsack Problem. If you give a dynamic programming algorithm, state the
    precise ``English'' definitions of your sub-problems, state base cases, and the recurrence. Try to make it
    as efficient as you can. Prove its correctness and analyze its running time. Does it run in polynomial
    time?
    \label{it:knapalg}
  \item Define the~\emph{$\epsilon W$-Knapsack Problem} for a fixed constant~$\epsilon$ as the Knapsack
    Problem above, except that you have the guarantee that, in the input, we have~$\epsilon W\leq w_i$ for
    every~$i\in S$ (i.e., there are no arbitrarily small weights). Can you come up with a polynomial time
    algorithm for this problem? Or is your algorithm for part~\ref{it:knapalg} already polynomial time for
    this problem? Why? Analyze. (Note: the expected answer is short and~$\epsilon$ is \emph{not} part of the
    input.)
    \label{it:epsilonW}
  \item Define the~\emph{$\epsilon V$-Knapsack Problem} for a fixed constant~$\epsilon$ as the Knapsack
    Problem above, except that you have the guarantee that, in the input, we have~$\epsilon V\leq v_i$ for
    every~$i\in S$ (i.e., there are no arbitrarily small values). Can you come up with a polynomial time
    algorithm for this problem? Why? Analyze. (Note: the expected answer is short and~$\epsilon$ is \emph{not}
    part of the input.)
    \label{it:epsilonV}
  \end{enumerate}
\end{exercise}

\begin{solution}
  Before we present the algorithm for item~\ref{it:knapalg}, we will prove some properties. First, we assume
  without loss of generality that~$S = \{1,\ldots,n\}$.

  First, for~$i\in\{1,\ldots,n\}$ and~$w\in\{0,\ldots,W\}$, let
  \begin{align*}
    B(i,w) & = \max\left\{\sum_{j\in J} v_j : J\subseteq\{1,\ldots,i\}\land\sum_{j\in J} w_j\leq w\right\}.
  \end{align*}

  We now prove a small lemma.
  \begin{lemma}\label{lem:dp}
    For every~$i\in\{1,\ldots,n\}$ and~$w\in\{0,\ldots,W\}$, we have
    \begin{align*}
      B(i,w) & =
      \begin{dcases*}
        \max\{B(i-1, w), B(i-1, w-w_i) + v_i\}, & if~$i\geq 2$ and~$w\geq w_i$;\\
        B(i-1, w), & if~$i\geq 2$ and~$w < w_i$;\\
        v_i, & if~$i=1$ and~$w\geq w_i$;\\
        0, & if~$i=1$ and~$w < w_i$.
      \end{dcases*}
    \end{align*}
  \end{lemma}

  \begin{proof}
    The assertions when~$i=1$ are trivial.

    Suppose then that~$i\geq 2$.

    %% and that the assertion holds for~$B(j,w)$ with~$j < i$ (and
    %% all~$w\in\{0,\ldots,W\}$) by induction.

    Clearly we must have~$B(i,w)\geq B(i-1,w)$ be the definition of~$B$.

    Suppose first that~$w < w_i$ and let us prove the other inequality~$B(i,w)\leq
    B(i-1,w)$. Let~$J\subseteq\{1,\ldots,i\}$ be such that~$\sum_{j\in J} v_i = B(i,w)$ and~$\sum_{j\in
      J}w_j\leq w$. Since~$w_i > w$, we know that~$i\notin J$, which immediately implies~$B(i-1,w)\geq
    \sum_{j\in J} v_j = B(i,w)$ as desired.

    Therefore, when~$w < w_i$ and~$i\geq 2$, we have~$B(i,w)=B(i-1,w)$.

    It remains to prove the case~$i\geq 2$ and~$w\geq w_i$. We have already proved that~$B(i,w)\geq
    B(i-1,w)$. Let~$J\subseteq\{1,\ldots,i-1\}$ be such that~$\sum_{j\in J} v_i = B(i-1,w-w_i)$
    and~$\sum_{j\in J} w_j\leq w - w_i$. Then we have~$\sum_{j\in J\cup\{i\}} w_j\leq w$, which
    implies~$B(i,w)\geq \sum_{j\in J\cup\{i\}}v_j = B(i-1,w-w_i) + v_i$. Putting this together with the
    previously proved inequality, we get
    \begin{align*}
      B(i,w) & \geq \max\{B(i-1,w), B(i-1,w-w_i) + v_i\}.
    \end{align*}

    Let us now prove the other inequality. Let~$J\in\{1,\ldots,i\}$ be such that~$\sum_{j\in J} v_j = B(i,w)$
    and~$\sum_{j\in J} w_j\leq w$.

    If~$i\in W$, then we have~$\sum_{j\in J\setminus\{i\}} w_j\leq w - w_i$, which
    implies~$B(i-1,w-w_i)\geq\sum_{j\in J\setminus\{i\}} v_j = B(i,w) - v_i$. Hence~$B(i,w)\leq B(i-1,w-w_i) +
    v_i$, which implies~$B(i,w)\leq\max\{B(i-1,w), B(i-1,w-w_i)+v_i\}$.

    On the other hand, if~$i\notin W$, then~$J\subseteq\{1,\ldots,i-1\}$, which implies~$B(i-1,w)\geq
    \sum_{j\in J} v_j = B(i,w)$, hence~$B(i,w)\leq\max\{B(i-1,w), B(i-1,w-w_i)+v_i\}$.

    Therefore we get
    \begin{align*}
      B(i,w) & = \max\{B(i-1,w), B(i-1,w-w_i) + v_i\},
    \end{align*}
    as desired.
  \end{proof}

  Based on Lemma~\ref{lem:dp}, since the solution of the problem is simply computing~$B(n,W)$ and testing
  whether it is greater or equal to~$V$. Consider then the following algorithm.

  \begin{algorithm}[H]
    \caption{Knapsack}
    \label{alg:knap}
    \DontPrintSemicolon
    \lFor{$w\leftarrow 1$ \KwTo $w_i$}{$B[1,w]\leftarrow v_1$}
    \lFor{$w\leftarrow w_i+1$ \KwTo $W$}{$B[1,w]\leftarrow 0$}
    \For{$i\leftarrow 2$ \KwTo $n$}{
      \lFor{$w\leftarrow 1$ \KwTo $w_i$}{$B[i,w]\leftarrow\max\{B[i-1,w], B[i-1,w-w_i] + v_i\}$}
      \lFor{$w\leftarrow w_i+1$ \KwTo $W$}{$B[i,w]\leftarrow B[i-1,w]$}
    }
    \lIf{$B[n,W]\geq V$}{\Return ``Yes''}
    \lElse{\Return ``No''}
  \end{algorithm}

  Clearly the table~$B[i,w]$ in Algorithm~\ref{alg:knap} is filled in non-decreasing order
  of~$i$. Furthermore, by Lemma~\ref{lem:dp} (and an induction), it follows that~$B[i,w]$ is gets the
  value~$B(i,w)$, which implies that Algorithm~\ref{alg:knap} correctly solves the Knapsack Problem.

  It is also straightforward to see that the complexity of Algorithm~\ref{alg:knap} is~$O(n\cdot W\cdot b_v)$,
  where~$b_v$ is the maximum bitlength among~$v_1,\ldots,v_n,V$.

  Unfortunately, the input size is~$O(n\cdot\log W\cdot b_v)$, which implies that Algorithm~\ref{alg:knap} is
  not polynomial.

  \medskip

  Before we solve the other items, consider the following problem.

  Let~$k\in\NN$ be fixed. The~\emph{$k$-Knapsack Problem} is the same as the Knapsack Problem, except that we
  also require~$\lvert S'\rvert\leq k$, that is, we want to find a collection of \emph{at most~$k$} items of
  maximum value, not exceeding the maximum weight (here~$k$ is \emph{not} part of the input and is fixed).

  Note now that if~$\lvert S\rvert = n$, then
  \begin{align*}
    \lvert\{S'\subseteq S : \lvert S'\rvert\leq k\}\rvert & = \sum_{i=0}^k n^i = O(n^k).
  \end{align*}

  This immediately implies that the following algorithm correctly solves the~$k$-Knapsack Problem in
  time~$O(n^{k+1}\cdot b)$, where~$b$ is the maximum bitlength of~$w_1,\ldots,w_n,v_1,\ldots,v_n,W,V$.

  \begin{algorithm}[H]
    \caption{$k$-Knapsack}
    \label{alg:kknap}
    \DontPrintSemicolon
    \For{$J\subseteq\{1,\ldots,n\}$ with~$\lvert J\rvert\leq k$}{
      \If{$\sum_{j\in J} w_j \leq W$}{
        \If{$\sum_{j\in J} v_j \geq V$}{
          \Return ``Yes''.\;
        }
      }
    }
    \Return ``No''.\;
  \end{algorithm}

  We can now solve the other items.

  First, note that for item~\ref{it:epsilonW}, since we are guaranteed that~$w_i\geq\epsilon W$, then we know
  that any~$J\subseteq\{1,\ldots,n\}$ with~$\sum_{j\in J} w_j\leq W$ must have at most~$\floor{1/\epsilon}$
  items, which implies that Algorithm~\ref{alg:kknap} with~$k = \floor{1/\epsilon}$ correctly solves
  the~$\epsilon W$-Knapsack Problem in time~$O(n^{1/\epsilon}\cdot b)$, which is polynomial since~$\epsilon$
  is not part of the input.

  Note that Algorithm~\ref{alg:knap} of item~\ref{it:knapalg} does not run in polynomial time even with the
  guarantee that~$w_i\geq\epsilon W$.

  \medskip
  
  For item~\ref{it:epsilonV}, since we are guaranteed that~$v_i\geq\epsilon V$, then we know that if there
  exists~$J\subseteq\{1,\ldots,n\}$ with~$\sum_{j\in J} w_j\leq W$ and~$\sum_{j\in J} v_j\geq V$, then any
  subset~$J'\subseteq J$ with~$\lvert J'\rvert\geq 1/\epsilon$ must also satisfy~$\sum_{j\in J'} w_j\leq W$
  and~$\sum_{j\in J'} v_j\geq V$. This implies that Algorithm~\ref{alg:kknap} with~$k=\floor{1/\epsilon}$
  correctly solves the~$\epsilon V$-Knapsack Problem in time~$O(n^{1/\epsilon}\cdot b)$, which is polynomial.
\end{solution}

\begin{exercise}
  We are given an array~$A[1..n]$ of~$n$ rational numbers with~$n\geq 3$ and the special property
  that~$A[1]\geq A[2]$ and~$A[n-1]\leq A[n]$. We say that an element~$A[x]$ is a \emph{local minimum of~$A$}
  if~$A[x-1]\geq A[x]$ and~$A[x]\leq A[x+1]$. First, note that, given the condition~$A[1]\geq A[2]$
  and~$A[n-1]\leq A[n]$, the array~$A$ must have at least one local minimum, and it is trivial to find it
  in~$O(b\cdot n)$ time, where~$b$ is the largest bitlength of an element of~$A$. Give an algorithm to find
  and return a local minimum of~$A$ in~$O(b\cdot(\log n)^2)$ time. Analyze the running time of your
  algorithm. Prove the correctness of your algorithm.
\end{exercise}

\begin{solution}
  Consider the following algorithm.

  \begin{algorithm}[H]
    \caption{Local minimum}
    \label{alg:lmin}
    \DontPrintSemicolon
    \lIf{$n = 3$}{\Return $1$.}
    \If{$n = 4$}{
      \lIf{$A[2]\leq A[3]$}{\Return $2$.}
      \Return $3$.\;
    }
    $i \leftarrow \ceil{n/2}$.\;
    \lIf{$A[i-1] < A[i]$}{\Return $\operatorname{Local minimum}(A[1..i])$.}
    \lIf{$A[i] > A[i+1]$}{\Return $i - 1 + \operatorname{Local minimum}(A[i..n])$.}
    \Return $i$.\;
  \end{algorithm}

  First note that if~$n\geq 5$, then we must have~$3 \leq \ceil{n/2}\leq n - 2$, which implies that the
  recursive calls effectively reduce the size of the array and yield an array of size at
  least~$3$. Furthermore, the conditions for the recursive calls ensure that the array~$A'$ passed recursively
  satisfies~$A'[1]\geq A'[2]$ and~$A'[n'-1]\leq A'[n']$ (where~$n'$ is the size of~$A'$).

  It is easy to see that Algorithm~\ref{alg:lmin} correctly solves the problem if~$n=3$ or~$n=4$.

  On the other hand, if~$n\geq 5$ and we assume by induction that Algorithm~\ref{alg:lmin} correctly solves
  the problem for arrays of size strictly less than~$n$, then we have two cases.

  In the first case, the point~$i = \ceil{n/2}$ is a local minimum and clearly the algorithm correctly finds
  it (the last two ``ifs'' test false).

  In the second case, the point~$i = \ceil{n/2}$ is not a local minimum, so we must either have~$A[i-1] <
  A[i]$ or~$A[i] > A[i+1]$. The first implies that~$A$ has a local minimum in~$2,\ldots,i-1$, which, by
  inductive hypothesis, is correctly found by the recursive call. The latter implies that~$A$ has a local
  minimum in~$i+1,\ldots,n$, which by inductive hypothesis (and noting that we correctly adjust the index
  returned), is correctly found by the recursive call.

  Therefore, Algorithm~\ref{alg:lmin} correctly solves the problem.

  \medskip

  Let us now analyze the time complexity of the algorithm. Let~$T(n,b)$ be the time complexity of
  Algorithm~\ref{alg:lmin} when~$A$ has~$n$ entries, each with bitlength at most~$b$. By inspecting the
  algorithm (and since~$n-\ceil{n/2} = \floor{n/2}$), it is clear that we have
  \begin{align}\label{eq:Trec}
    T(n,b)\leq \max\left\{T\(\ceil{\frac{n}{2}},b\),T\(\floor{\frac{n}{2}}+1,b\)\right\} + O(b\log n)
  \end{align}
  whenever~$n\geq 5$.

  (We will solve this recursion completely formally. Usually one handwaves some of what follows.)
  
  Consider the function~$U(n,b)$ defined inductively by letting
  \begin{align*}
    U(3,b) & = U(4,b) = \max\{T(3,b),T(4,b)\}
  \end{align*}
  and
  \begin{align*}
    U(n,b)
    & =
    \max\left\{U\(\ceil{\frac{n}{2}},b\),U\(\floor{\frac{n}{2}}+1,b\)\right\} + C\cdot b\log n,
  \end{align*}
  for~$n\geq 5$, where~$C > 0$ is a constant such that the function~$g$ that is~$O(b\log n)$
  in~\eqref{eq:Trec} satisfies~$g(n)\leq C b\log_2(n-1)$ for every~$n\geq 3$ (this is possible since~$O(b\log
  n)$ is the same as~$O(b\log_2(n-1))$).

  We claim that~$T(n,b)\leq U(n,b)$ for all~$n\geq 3$ and all~$b\geq 1$. This is clearly true if~$n\leq 4$.

  Suppose then that~$n\geq 5$ and that~$T(m,b)\leq U(m,b)$ for every~$m < n$ by induction. Then
  since~$3\leq\ceil{n/2}\leq\floor{n/2}+1\leq n-1$, equation~\ref{eq:Trec} implies
  \begin{align*}
    T(n,b) \leq \max\left\{U\(\ceil{\frac{n}{2}},b\),U\(\floor{\frac{n}{2}}+1,b\)\right\} + C\cdot b\log_2(n-1)
    = U(n,b),
  \end{align*}
  as desired.

  Therefore~$T(n,b)\leq U(n,b)$ for all~$n\geq 3$ and all~$b\geq 1$. In particular, we have~$T = O(U)$.

  We now claim that~$U$ is non-decreasing in the first coordinate. We clearly have~$U(3,b)\leq
  U(4,b)$. Suppose then that~$n\geq 5$ and that~$U(m-1,b)\leq U(m,b)$ for every~$m < n$ by induction. Then
  since~$3\leq\ceil{n/2}\leq\floor{n/2}+1\leq n-1$, we have
  \begin{align*}
    U(n,b) & = \max\left\{U\(\ceil{\frac{n}{2}},b\),U\(\floor{\frac{n}{2}}+1,b\)\right\} + C\cdot b\log_2(n-1)
    \\
    & \geq
    \max\left\{U\(\ceil{\frac{n-1}{2}},b\),U\(\floor{\frac{n-1}{2}}+1,b\)\right\} + C\cdot b\log_2(n-2)
    \\
    & = U(n-1,b),
  \end{align*}
  since~$\log_2$ is increasing.

  Therefore~$U(n-1,b)\leq U(n,b)$ for every~$n\geq 4$ and every~$b\geq 1$.

  Let us now prove by induction in~$k\geq 1$ that~$U(2^k+1,b) \leq U(3,b) + C\cdot b\cdot k^2$.

  For~$k = 1$, this is trivial. So suppose~$k\geq 2$ and that the result holds for~$k-1$. Then we have
  \begin{align*}
    U(2^k+1,b) & = \max\{U(2^{k-1}+1,b), U(2^{k-1}+1,b)\} + C\cdot b\cdot\log_2(2^k)
    \\
    & \leq U(3,b) + C\cdot b\cdot (k-1)^2 + C\cdot b\cdot k
    \\
    & \leq C\cdot b\cdot k^2,
  \end{align*}
  as desired.

  We now claim that~$U(n,b) = O(b\cdot(\log n)^2)$.

  First note that for~$n = 2^k + 1$ for some~$k\geq 1$, we have already proved~$U(n,b) \leq C\cdot b\cdot(\log
  n)^2$.

  On the other hand, if~$n\geq 3$ is not of the form~$2^k + 1$ for some~$k\geq 1$, then there at least
  exists~$k\geq 1$ such that~$n\leq 2^k+1\leq 2n$. Since~$U$ is non-decreasing in the first coordinate, we get
  \begin{align*}
    U(n,b) & \leq U(2^k+1,b) \leq C\cdot b\cdot k^2
    \leq
    C\cdot b\cdot (\log(2n-1))^2.
  \end{align*}

  Therefore~$U(n,b) = O(b\cdot(\log n)^2)$, which implies~$T(n,b) = O(b\cdot(\log n)^2)$.
\end{solution}

\begin{exercise}
  A \emph{cycle} in an undirected simple graph~$G = (V,E)$ is a sequence of vertices
  \begin{align*}
    (v_0,v_1,\ldots,v_k)
  \end{align*}
  with~$v_0 = v_k$, $k\geq 3$ and~$\{v_i,v_{i+1}\}\in E(G)$, $v_i\neq v_{i+1}$ and~$v_i\in V(G)$ for
  every~$i\in\{0,1,\ldots,k-1\}$.

  In this exercise, we consider that access to a graph~$G$ with vertex set~$V(G) = \{1,\ldots,n\}$ is given by
  the following subroutines.
  \begin{itemize}
  \item The subroutine~$\operatorname{vertices}()$ returns the number of vertices~$n$ in time~$O(\log n)$
    (which is the bitlength of~$n$).
  \item The subroutine~$\operatorname{nextneighbor}(i,j)$ returns the smallest~$k\geq j$ such that~$\{i,k\}\in
    E(G)$ and returns ``NONE'' if no such~$k$ exists. This subroutine also takes time~$O(\log n)$.
  \end{itemize}

  Design an algorithm that, using the subroutines above, runs in time~$O(n\log n)$ and returns a cycle of the
  graph~$G$ if one exists and returns ``ACYCLIC'' if~$G$ does not contain any cycle. Prove the correctness of
  your algorithm.

  Observation: the graph may have much more than~$O(n)$ edges (it can have up to~$\Omega(n^2)$ edges), so your
  algorithm cannot inspect all edges of the graph. Note also that your algorithm can only make at most~$O(n)$
  calls to the subroutines above.
\end{exercise}

\begin{solution}
  Let us suppose that~$V(G) = \{1,\ldots,n\}$ and consider the following algorithm.

  \begin{algorithm}[H]
    \caption{Detect cycle}
    \label{alg:cycle}
    \DontPrintSemicolon
    $n\leftarrow\operatorname{vertices}()$.\;
    \lFor{$i\leftarrow 1$ \KwTo $n$}{$V[i]\leftarrow 0$}
    Let~$S$ be an empty stack.\;
    \For(\label{lin:for}){$s\leftarrow 1$ \KwTo $n$}{
      \If{$V[s] = 0$}{
        Push~$(s,1)$ to~$S$.\;
        $V[s]\leftarrow 1$.\;
        \While(\label{lin:while}){$S$ is not empty}{
          Pop the top element~$(v,i)$ from~$S$.\label{lin:popv}\;
          $i\leftarrow\operatorname{nextneighbor}(v,i)$.\label{lin:findneighbor}\;
          \If(\label{lin:i=v}){$S$ is non-empty and~$i = z$ for the top element~$(z,k)$ of~$S$}{
            $i\leftarrow\operatorname{nextneighbor}(v,i)$.\;
          }
          \If(\label{lin:ifinotNONE}){$i\neq{}$``NONE''}{
            \If(\label{lin:V}){$V[i] = 1$}{
              $w_1\leftarrow v$\;
              $k\leftarrow 2$\;
              \While(\label{lin:cycle}){The top element of~$S$ is not~$(i,j)$ for some~$j$}{
                Pop the top element~$(w,j)$ of~$S$.\;
                $w_k\leftarrow w$\;
                $k\leftarrow k+1$\;
              }
              $w_k\leftarrow i$\;
              \Return $(w_1,w_2,\ldots,w_k,v)$\;
            }
            \Else(\label{lin:else}){
              Push~$(v,i+1)$ to~$S$.\label{lin:push+1}\;
              Push~$(i,1)$ to~$S$.\label{lin:ienters}\;
              $V[i]\leftarrow 1$\;
            }
          }
        }
      } 
    }
    \Return ``ACYCLIC''.\;
  \end{algorithm}

  Let us prove the correctness of the algorithm above.

  First we claim thatif the elements of the stack~$S$ are~$((v_1,i_1),\ldots,(v_k,i_k))$ at some point,
  then~$\{v_j,v_{j+1}\}\in E(G)$ for every~$j\in\{1,\ldots,k-1\}$.

  This is clearly true if~$S$ is empty or has at most one element, so this holds when the algorithm enters the
  loop of line~\ref{lin:while} for the first time. Note that the only other place in which elements are pushed
  on~$S$ is in the else line~\ref{lin:else}, in this case, the algorithm popped~$(v,i)$ in line~\ref{lin:popv} and
  ensured through lines~\ref{lin:findneighbor}, \ref{lin:i=v} and~\ref{lin:ifinotNONE} that~$i$ is changed to a
  value such that~$\{v,i\}\in E(G)$. In the else of line~\ref{lin:else}, the algorithm then pushes~$(v,i)$
  then~$(i,1)$. If~$(w,j)$ is the element before~$(v,i)$ in~$S$, we have~$\{v,w\}\in E(G)$ by induction
  (before~$v$ was popped from~$S$) and we proved that~$\{v,i\}\in E(G)$.

  Therefore the claim holds.

  Let us call a pair~$(w,j)$ a representative of~$v$ if~$w = v$.

  We claim that for every~$v\in V(G)$, at all points the stack~$S$ can have at most one representative of~$v$.

  First note that for the push operation of line~\ref{lin:push+1} to happen, the pop operation of
  line~\ref{lin:popv} must have happened. This means that line~\ref{lin:push+1} can only replace
  representatives of~$v$, but not add them. Furthermore, it always replaces them with a representative~$(v,j)$
  with~$j\geq 2$. Hence, the only form in which a representative of~$v$ enters~$S$ without replacing one is if
  it is of the form~$(v,1)$. But for~$(v,1)$ to be pushed on~$S$, we must have had~$V[v]=0$ and it is
  immediately set to~$1$ afterward, so it can be pushed on~$S$ at most once.

  Therefore at all points the stack~$S$ can have at most one representative of~$v$.

  Note also that since when we replace a representative~$(v,j)$ of~$v$ by another~$(v,r)$ on
  line~\ref{lin:push+1}, we always have~$r > j$, so it follows that each pair~$(v,j)\in V(G)\times V(G)$ can
  enter~$S$ at most once.

  Note furthermore that the only pairs that can be pushed on~$S$ are of the form~$(v,i+1)$ with
  either~$\{v,i\}\in E(G)$ or~$i = 0$. 

  Let us say that~$v$ enters~$S$ when some representative of~$v$ enters~$S$. Let us say that~$v$ leaves~$S$
  when line~\ref{lin:ifinotNONE} tests false in the same iteration when line~\ref{lin:popv} popped a
  representative of~$v$ (this way we do not count when representatives of~$v$ are replaced).

  We claim that for every~$v\in V(G)$, if~$v$ leaves~$S$, then each neighbor of~$v$ must have
  entered~$S$ in some iteration before~$t$. Consider all the representatives of~$v$ that enter~$S$ in
  order~$(v,i_0),(v,i_1),\ldots,(v,i_\ell)$.

  We know that~$i_0=1$ and~$\{v,i_r-1\}\in E(G)$ for all~$r\in\{1,\ldots,\ell\}$. But also note that in the
  iteration when~$(v,i_r)$ is pushed on~$S$ we also push~$(i_r,1)$ on~$S$, the pair~$(v,i_{r-1})$ must have
  been popped, and for every~$i_{r-1}\leq k < i_r$, we either have~$\{v,k\}\notin E(G)$ or~$k$ is was in the
  top of~$S$ after the pop of line~\ref{lin:popv}.

  Therefore all neighbors of~$v$ must enter~$S$ before~$v$ leaves~$S$.

  Let us now prove that if line~\ref{lin:V} tests true (i.e., we have~$V[i] = 1$), then there must exist a
  representative of~$i$ in~$S$.

  First note that line~\ref{lin:V} can test true only at most once since it has a return statement in its
  block. Since~$V[i]=1$, we know that at some point~$i$ must have entered~$S$. But in the iteration when
  line~\ref{lin:V} tests true, line~\ref{lin:ifinotNONE} must have also tested true, which means that~$v$ has not
  yet left~$S$ and since~$i$ is a neighbor of~$v$, it follows that~$i$ also has not yet left~$S$. Therefore
  there must exist a representative of~$i$ in~$S$.

  Note that this implies that the loop of line~\ref{lin:cycle} actually ends. This along with the fact that
  each pair~$(v,i)$ can enter~$S$ at most once implies that the algorithm always halts.

  Note also that if~$S$ before this loop was~$(v_1,i_1),\ldots,(v_r,i_r)$ with~$i = i_\ell$ and the top
  being~$(v_1,i_1)$, then by the end of the loop we have~$k = \ell-1$ and~$v_s = w_{s+1}$ for
  all~$s\in\{1,\ldots,k\}$, which implies (by our first claim) that~$(w_1,w_2,\ldots,w_k,v)$ is a cycle of~$G$
  since~$w_1= v$, $w_k = i$ and~$\{v,i\}\in E(G)$.

  Therefore, if the algorithm returns a cycle, then it is indeed a cycle in~$G$.

  Define now the graphs~$G_t$ inductively as follows. We first let~$G_0$ be the graph without any vertices and
  we follow the execution the execution of Algorithm~\ref{alg:cycle} and each time some vertex~$i$ enters~$S$,
  we define~$G_{t+1}$ from~$G_t$ by adding~$i$ to~$V(G_t)$ and if~$v$ entered~$S$ in line~\ref{lin:ienters},
  we also add the edge~$\{v,i\}$ to~$G_{t-1}$.

  It is easy to see that at any point the vertices of~$G_t$ are precisely the~$v\in V(G)$ such
  that~$V[v]=1$. Furthermore, since each edge added is an edge of~$G$, the graph~$G_t$ is always a subgraph
  of~$G$. Also, each edge added is incident to a new vertex, so~$G_t$ does not have any cycles.

  But since the maximum number of edges an acyclic graph on~$n$ vertices can have is~$n-1$, it follows that we
  only ever define~$G_t$ for~$t\leq n-1$. On the other hand, on each iteration of the while of
  line~\ref{lin:while}, either a vertex leaves~$S$ or a vertex enters~$S$, so it must run a total of at
  most~$2n-2$ times, each of which has time complexity~$O(\log n)$, except if the loop of line~\ref{lin:cycle}
  runs. But the loop of line~\ref{lin:cycle} runs at most once in total, and it has complexity~$O(n\log n)$
  (as the stack never has more than~$n$ elements). The loop of line~\ref{lin:for} clearly runs~$n$
  times.

  Therefore, we get that the algorithm has time complexity of~$O(n\log n)$.

  It remains to prove that if the algorithm returns ``ACYCLIC'', then~$G$ does not have any cycle.

  Suppose that the algorithm returns ``ACYCLIC'', then the test of line~\ref{lin:V} is always false.

  From the first lines of the loop of line~\ref{lin:for}, it follows that every vertex must eventually
  enter~$S$, hence must eventually enter some~$G_t$. On the other hand, since the loop of line~\ref{lin:while}
  ends without line~\ref{lin:V} testing true, it follows that every vertex must eventually leave~$S$.

  We claim that every edge of~$G$ is in some~$G_t$.

  Fix some edge~$\{u,w\}\in E(G)$ and suppose~$u$ enters~$S$ before~$w$. Consider all the representatives
  of~$w$ that enter~$S$ in order~$(w,i_0),(w,i_1),\ldots,(w,i_\ell)$ and let~$r\geq 0$ be the maximum such
  that~$i_r\leq u$.

  Consider the iteration when~$(w,i_r)$ is popped from~$S$. At this point~$u$ is in~$S$ since it entered
  before~$w$ and can only leave after~$w$ leaves (since the representatives of~$w$ keep getting replaced
  and the representative of~$u$ is further down on the stack). Since the test of line~\ref{lin:V} is false
  and~$\operatorname{nextneighbor}(w,i_r) = u$, it follows that the test of line~\ref{lin:i=v} must have been
  true, which implies that in the beginning of the iteration the two top elements of~$S$ where~$(w,i_r)$ and a
  representative of~$u$. This implies that~$(w,i_0)=(w,1)$ must have been pushed on line~\ref{lin:ienters} in
  an iteration when~$v=u$ and~$i=w$, which implies that we added the edge~$\{u,w\}$ to some~$G_t$.

  Let~$T$ be the maximum such that we defined~$G_T$. Since all edges of~$G$ are eventually added to
  some~$G_t$, it follows that~$G_T = G$, but~$G_T$ does not have any cycle, so~$G$ does not have any cycle as
  desired.
\end{solution}

%\log(n)^2 on Ex 2.
%Does not repeat vertices on Ex 3. Length at least 3.

\end{document}

%%  LocalWords:  vertices bitlength handwaves