% \begin{frame}
%     \frametitle{\problemtitle}
%     \begin{description}
%         \item<+->[Problem:]
% 	  In an undirected unweighted simple graph, find a shortest walk from $v_1$ back to $v_1$ using at least one edge and without a \emph{digon} (i.e., without a subwalk of the form $u, v, u$).
%         \item<+->[Observation:]
% 	  The solution necessaraly forms a \emph{tadpole} graph starting in $v_1$.
% 	  That is, it consists of a simple path $P=v_1,\ldots, v_r$, possibly with $v_1=v_r$, and a simple cycle $C$ of at least $3$ edges such that $V(P)\cap V(C)= \{v_r\}$.
%         \item<+->[Proof:] Clearly a tadpole graph describes a valid solution by tracing it in the obvious way.
% 	  For the other direction, assume that $W=w_1,\ldots, w_s$ with $w_s=w_1=v_1$ is a solution.
% 	  We shall observe that $W$ describes a tadpole.
% 	  Let $j$ be the largest index the walk prefix $w_1,\ldots,w_j$  and suffix
% 	  $w_s, \ldots, w_{s-j}$ agree.
% 	  Note that $j< \lceil s/2\rceil$ because otherwise $W$	would contain the digon $w_j,w_j+1, w_{s-j}$ or $w_{j-1}, w_j=w_{s-j}, w_{s-j-1}$.
% 	  Thus, $w_j,\ldots, w_{s-j}$ is a closed subwalk has length at least $3$ edges.
% 	  Since $W$ has minimal length, this subwalk must form a simple cycle $C$.
% 	  Finally, it contains no vertices from $w_1,\ldots, w_{j-1}$, because otherwise there would be a shorter solution.

%         \item<+->[Running time:] $\mathcal O(1)$.
%     \end{description}
%     \solvestats
% \end{frame}

\begin{frame}
    \frametitle{\problemtitle}
    \begin{description}
        \item<+->[Problem:]
	  In an undirected unweighted simple graph, find a shortest walk from $v_1$ back to $v_1$ using at least one edge and without a \emph{digon} (i.e., without a subwalk of the form $u, v, u$).
        \item<+->[Idea:] Assume there is a valid solution, and look at a node $w$ on the path that is \emph{furthest} from $v_1$ (i.e. the node with the greatest depth from $v_1$).
        \item<+->[Observation:] From this node, two paths to $v_1$ must exist that start out towards different neighbours of $w$.
        \item<+->[Observation 2:] In the optimal solution, the sum of the lengths of these paths must be minimal.
        \item<+->[Observation 3:] The length of such a path is $1$ plus the depth of the neighbour of $w$ the path goes through.
        \item<+->[Observation 4:] These paths go to the two neighbours of $w$ that are closest to $v_1$.
    \end{description}
\end{frame}

\begin{frame}
    \frametitle{\problemtitle}
    
    \centering
    \includegraphics[width=0.7\linewidth]{fig2.pdf}
    \captionof{figure}{The two cases for optimal solutions given a furthest node.}
\end{frame}

\begin{frame}
    \frametitle{\problemtitle}
    \begin{description}
        \item<+->[Solution:] Run a BFS and check the optimal path length for all possible deepest nodes:
        \item<+->[] Mark the depth of each node.
        \item<+->[] When encounting a node for the second time, the path length is the depth
                    of the node plus the path length of the second path to this node.

        \item<+->[] Pick the optimal deepest node (if one exists) and reconstruct the path.
        \item<+->[Running time:] $\mathcal O(n+m)$
    \end{description}
    \solvestats
\end{frame}







% Every valid path has one or more furthest points. Let's fix one such point.
% From such a point, two paths to start must exist that "start in different directions"
% An optimal solution that includes this node as a furthest point must consist of two paths from this node with a minimal combined length.
% We can't go deeper, and we can always go up, so the optimal solution is either going up twice, or going up and going horizontal.

% solution:
% run a BFS
% mark depth of nodes
% when you encounter a node a second time, you have found a valid path
% path length = sum depths of nodes + 1
% fun fact: tadpole graph

% Optimal path will be a tadpole graph: some path to a cycle where you "turn around"
% Every optimal solution has a point (possibly two points) that's furthest from the start one the cycle
% From this furthest point, there must be two paths back to the start

% solution:
% run a BFS from start
% - when you first encounter a node, mark its depth (i.e. distance to start)
% - when you encounter a node a second time (i.e. from an equally deep node or a node that's one closer but not the parent)
%   you have found a tadpole graph
%   length is depth of one node + depth of other node + 1 (the edge connecting them)
% - take an optimal node and reconstruct the path