Start report practical 1

5 files changed, 485 insertions, 0 deletions

diff --git a/Practical1/report/algorithm.tex b/Practical1/report/algorithm.tex
new file mode 100644
index 0000000..6a079ea
--- /dev/null
+++ b/Practical1/report/algorithm.tex
@@ -0,0 +1,259 @@
+\section{Algorithm description}
+\label{sec:algorithm}
+
+\subsection{Basic structure}
+\label{sec:algorithm:basic-structure}
+The basic structure of the algorithm is fairly simple. For any graph $G=(V,E)$, we pick a vertex $v\in V$. Either that vertex is in an m.i.s. (and none of its neighbours), or it is not. This gives the recurrence: \refeq[basic-structure]{\ms(G) = \max(1 + \ms(G\ex \iN(v)), \ms(G\ex v)).} The rest of the algorithm will be optimising this basic structure by cleverly choosing $v$ and pruning the search tree.
+
+\begin{lemmaproof}[one-neighbour]{For a graph $G=(V,E)$ and vertex $v\in V$, if $v$ is not in an m.i.s. there is a neighbour $w\in N(v)$ which is in an m.i.s.}
+    By contradiction. Suppose there were an m.i.s. $ms_1$ that does not contain $v$ or one of its neighbours. Then we may create a new m.i.s. $ms_2=ms_1\with v$. We then have $|ms_2| = |ms_1|+1 > |ms_1|$. Therefore, $ms_1$ was not maximal.
+\end{lemmaproof}
+
+\begin{lemmaproof}[two-neighbours]{For a graph $G=(V,E)$ and vertex $v\in V$, there is an m.i.s. with $v$, or there is an m.i.s. with two distinct elements $w_1,w_2\in N(v)$.}
+    By contradiction. If $v$ is in an m.i.s., we're done. If $v$ is not in an m.i.s., we know by \autoref{lem:one-neighbour} that there is a $w_1\in N(v)$ that is, say in m.i.s. $ms$. Suppose there were no other neighbour $w_2\in N(v), w_2\neq w_1$ with $w_2\in ms$. Then $ms\ex w_1\with v$ is also an m.i.s., and it does contain $v$.
+\end{lemmaproof}
+
+At this point we define, as Robson \cite{robson}, the function $\ms^n(G,S)$ which is the $\ms(G)$ given that the m.i.s. should contain at least $n$ elements of $S$.
+
+Based on \autoref{lem:one-neighbour} and \ref{lem:two-neighbours} we may then rewrite \autoref{eq:basic-structure} to \refeq[with-two-neighbours]{\ms(G) = \max(1+\ms(G\ex\iN(v)), \ms^2(G\ex v, N(v))).}
+
+\subsection{Picking a good $v$}
+\label{sec:algorithm:good-v}
+Until now, we have assumed that we have some vertex $v$. Let us now discuss how to pick a `good' $v$, i.e. one that allows for the most efficient use of \autoref{eq:basic-structure} and \ref{eq:with-two-neighbours}.
+
+\begin{lemmaproof}[basic-structure-high-degree]{It is most efficient to use \autoref{eq:basic-structure} with a $v$ with large $d(v)$.}
+    The left-hand side, $\ms(G\ex\iN(v))$, will run faster with large $d(v)$, because it will run on a smaller graph. For the right-hand side it doesn't matter.
+\end{lemmaproof}
+
+\begin{lemmaproof}[two-neighbours-low-degree]{It is most efficient to use \autoref{eq:with-two-neighbours} with a $v$ with small $d(v)$.}
+    A straightforward implementation of $\ms^2(G\ex v,N(v))$ will consider all pairs of vertices in $N(v)$, which is quadratic. In the left-hand side, $\ms(G\ex\iN(v))$ is only linearly faster with large $d(v)$. Therefore, we should prefer small $d(v)$.
+\end{lemmaproof}
+
+In general, we'd like to use \autoref{eq:with-two-neighbours}, because the right-hand side of the $\max$ is more restricted than in \autoref{eq:basic-structure}. However, if we have a $v$ with large $d(v)$, this may not be the case. 
+
+So, we should try to pick a $v$ with small $d(v)$. We apply \autoref{eq:with-two-neighbours} if $d(v)$ is small enough. If $d(v)$ is too large to ensure efficient usage of \autoref{eq:with-two-neighbours}, we apply \autoref{eq:basic-structure}.
+
+But this latter recurrence is clearly more efficient for \emph{large} $d(v)$. Therefore, if $d(v)$ is too large to use $v$ in \autoref{eq:with-two-neighbours}, we find one of its neighbours, say $w\in N(v)$, with the largest $d(w)$, and apply \autoref{eq:basic-structure} with that vertex. In the next recurrence, $d(v)$ will be at least one smaller, because $w$ has been removed, but in the case of a graph with many three-cycles, $d(v)$ may be much smaller. So, after at most a few applications of \autoref{eq:basic-structure} we may use the more efficient \autoref{eq:with-two-neighbours} again.
+
+\subsubsection{Dominance}
+\label{sec:algorithm:good-v:dominance}
+\begin{lemmaproof}[dominance]{If in graph $G$ with vertices $v,w$ we have $v>w$, we know that $\ms(G)=\ms(G\ex w)$.}
+    If there is an m.i.s. $ms$ with $w\in ms$, $ms\ex w\with v$ is an m.i.s. as well.
+\end{lemmaproof}
+
+If we then take $w$ instead of $v$ and use \autoref{eq:basic-structure}, it may be the case that $v>w$. In this case, we may bypass \autoref{eq:basic-structure} by applying the recurrence $\ms(G)=\ms(G\ex w)$ of \autoref{lem:dominance}. After this, it may be the case that we can apply \autoref{eq:with-two-neighbours} instead, since $d(v)$ will have been decreased by one.
+
+This gives us \autoref{alg:with-best-vertex}, which combines \autoref{eq:basic-structure} and \ref{eq:with-two-neighbours}.
+
+\begin{algorithm}[h]
+    \caption{Finding the size of the m.i.s. of a graph}
+    \label{alg:with-best-vertex}
+    \begin{algorithmic}[1]
+        \REQUIRE $G=(V,E)$
+        \IF{$|G|=1$}
+            \RETURN $|G|$ \COMMENT{Recursive base case}
+        \ELSE
+            \STATE $v\gets v\in V$ with minimal $d(v)$
+            \IF{$d(v)$ is small enough}
+                \RETURN $\max(1+\ms(G\ex\iN(v)), \ms^2(G\ex v,N(v)))$ \COMMENT{\autoref{eq:with-two-neighbours}}
+            \ELSIF{$v$ dominates $w$}
+                \RETURN $\ms(G\ex w)$
+            \ELSE
+                \STATE $w\gets w\in N(v)$ with maximal $d(w)$
+                \RETURN $\max(1+\ms(G\ex\iN(w)), \ms(G\ex w))$ \COMMENT{\autoref{eq:basic-structure}}
+            \ENDIF
+        \ENDIF
+    \end{algorithmic}
+\end{algorithm}
+
+\subsection{Strongly connected components}
+\label{sec:algorithm:components}
+\begin{lemmaproof}[components]{The size of the m.i.s. of a graph is equal to the sum of the sizes of the m.i.s. of all its strongly connected components.}
+    The union of the m.i.s. of the strongly connected components is an m.i.s. of the graph.
+
+    If there were a larger m.i.s. in the graph, there has to be a $v$ in a strongly connected component $C$ in that m.i.s. which is not in the m.i.s. of $C$. If we can add $v$ to the m.i.s. of $C$, that m.i.s. wasn't maximal. If we cannot, then the larger m.i.s. of the whole graph cannot be an independent set.
+\end{lemmaproof}
+
+Based on \autoref{lem:components} we may write \refeq[with-components]{\ms(G)=\sum_{c\in C} \ms(c),} where $C$ is the set of strongly connected components of $G$. It is not difficult to see that in case a graph has multiple strongly connected components, this recurrence is more efficient than \autoref{alg:with-best-vertex}.
+
+\subsection{Further optimisations}
+\label{sec:algorithm:further-optimisations}
+Although I have referred to Robson \cite{robson} and used his notation throughout this report, this is how far I got without his help. Robson then introduces a number of further optimisations. In this section, we use $G$ for the graph at hand and $v,w$ for the vertex with the lowest degree, and its neighbour with the highest degree, respectively.
+
+\begin{lemmaproof}[robson-ms-d1]{If $d(v)=1$, we know $\ms(G)=1+\ms(G\ex\iN(v))$.}
+    By contradiction. By \autoref{lem:one-neighbour} we know that if $v$ is not in any m.i.s., then $w$ is in an m.i.s., say $ms$. But then $ms\ex w\with v$ is also independent, and has the same size.
+\end{lemmaproof}
+
+For the case that $d(v)=2$ we write $w,w'$ for the neighbours of $v$.
+
+\begin{lemmaproof}[robson-ms-d2-edge]{If $d(v)=2$ and $e(w,w')$, we know $\ms(G)=1+\ms(G\ex\iN(v))$.}
+    By \autoref{lem:two-neighbours} we know that an m.i.s. will either contain $v$ or both $w$ and $w'$. But since $e(w,w')$, the latter cannot happen. Therefore, it must contain $v$ and neither of its neighbours.
+\end{lemmaproof}
+
+\begin{lemmaproof}[robson-ms-d2-noedge]{If $d(v)=2$ and $\lnot e(w,w')$, we know $$\ms(G) = \max(2+\ms(G\ex\iN(w)\ex\iN(w')), 1 + \ms^2(G\ex\iN(v), N^2(v))).$$}
+    By \autoref{lem:two-neighbours}, an m.i.s. contains either $v$ or both $w,w'$. In the second case, we remove $w$ and $w'$ and their neighbourhoods from the graph (the left-hand side of $\max$). In the first case, the m.i.s. cannot contain $w$ or $w'$ but must contain two of their neighbours other than $v$. If not, and there is an m.i.s. $ms$ with at most one such neighbour, $u$, then $ms\ex v\ex u\with w\with w'$ is also independent, and has the same size. This gives the right-hand side.
+\end{lemmaproof}
+
+\autoref{alg:with-best-vertex} combined with \autoref{lem:components}, \ref{lem:robson-ms-d1}, \ref{lem:robson-ms-d2-edge} and \ref{lem:robson-ms-d2-noedge} gives us \autoref{alg:with-robsons-optimisations}.
+
+\begin{algorithm}[h]
+    \caption{Finding the size of the m.i.s. of a graph}
+    \label{alg:with-robsons-optimisations} \label{alg:ms}
+    \begin{algorithmic}[1]
+        \REQUIRE $G=(V,E)$
+        \IF{$G$ has multiple strongly connected components}
+            \STATE $C\gets$ some strongly connected component
+            \RETURN $\ms(C) + \ms(G\ex C)$ \COMMENT{\autoref{lem:components}}
+        \ELSIF{$|G|=1$}
+            \RETURN $|G|$ \COMMENT{Recursive base case}
+        \ELSE
+            \STATE $v\gets v\in V$ with minimal $d(v)$
+            \STATE $w\gets w\in N(v)$ with maximal $d(w)$
+            \IF{$d(v)=1$}
+                \RETURN $1+\ms(G\ex\iN(v))$ \COMMENT{\autoref{lem:robson-ms-d1}}
+            \ELSIF{$d(v)=2$}
+                \STATE $w'\gets$ the other neighbour of $v$
+                \IF{$e(w,w')$}
+                    \RETURN $1+\ms(G\ex\iN(v))$ \COMMENT{\autoref{lem:robson-ms-d2-edge}}
+                \ELSE
+                    \RETURN $\max(2+\ms(G\ex\iN(w)\ex\iN(w')), 1+\ms^2(G\ex\iN(v),N^2(v)))$ \COMMENT{\autoref{lem:robson-ms-d2-noedge}}
+                \ENDIF
+            \ELSIF{$d(v)=3$}
+                \RETURN $\max(\ms^2(G\ex v,N(v)), 1+\ms(G\ex\iN(v)))$ \COMMENT{\autoref{eq:with-two-neighbours}}
+            \ELSIF{$v>w$}
+                \RETURN $\ms(G\ex w)$ \COMMENT{\autoref{lem:dominance}}
+            \ELSE
+                \RETURN $\max(\ms(G\ex w), 1+\ms(G\ex\iN(w)))$ \COMMENT{\autoref{eq:basic-structure}}
+            \ENDIF
+        \ENDIF
+    \end{algorithmic}
+\end{algorithm}
+
+\subsection{The helper function $\ms^n$}
+\label{sec:algorithm:helper-function}
+So far we have been using $\ms^n(G,S)$ as the size of the maximum independent set of $G$ given that it contains at least $n$ vertices in $S$. This section is devoted to arguing an efficient implementation of this helper function. In the above, we have only used $\ms^2$. Therefore, we do not need to go into details about the case $n\neq2$.
+
+We will write $s_1,s_2,\dots$ for the elements of $S$.
+
+\begin{lemmaproof}[helper-general]{In our algorithm, it always holds that $\ms^n(G,S)=\ms(G)$.}
+    We only call $\ms^n$ when we know for sure that $n$ elements of $S$ are in an m.i.s. of $G$.
+\end{lemmaproof}
+
+\autoref{lem:helper-general} may be used as a default case, when no clever optimisation can be found.
+
+\begin{lemmaproof}[helper-1]{If $|S|<n$, we know $\ms^n(G,S)=0$.}
+    It is impossible to pick $n$ edges from less than $n$.
+\end{lemmaproof}
+
+\begin{lemmaproof}[helper-2-edge]{If $|S|=2$ and $e(s_1,s_2)$, then $\ms^2(G,S)=0$.}
+    The only possibility to choose two vertices from $S$, choosing $s_1$ and $s_2$ does not give us an independent set.
+\end{lemmaproof}
+
+\begin{lemmaproof}[helper-2-noedge]{If $|S|=2$ and $\lnot e(s_1,s_2)$, then $\ms^2(G,S)=2+\ms(G\ex\iN(s_1)\ex\iN(S_2)$.}
+    We only have to consider the one possibility of choosing $s_1$ and $s_2$. Then we may remove their inclusive neighbourhoods from the graph.
+\end{lemmaproof}
+
+\begin{lemmaproof}[helper-3-naive]{If $|S|=3$, we have $\ms^2(G,S)=\max(\ms^2(G,S\ex s_1), \ms^2(G,S\ex s_2), \ms^2(G,S\ex s_3)).$}
+    We only have to consider three possibilities.
+\end{lemmaproof}
+
+\autoref{lem:helper-general} through \ref{lem:helper-3-naive} were the results I achieved. Robson \cite{robson} adds some optimisations to the cases $|S|=3$ and $|S|=4$. As they are fairly straightforward, I will not discuss them here. They are included in \autoref{alg:ms2}, which combines our own results into one algorithm. Robson uses slightly different notation at some points, since he assumes $d(s_1)<d(s_2)$.
+
+\begin{algorithm}[h!]
+    \caption{Finding the size of the m.i.s. of a graph, given that it should contain two nodes from a certain subgraph}
+    \label{alg:ms2}
+    \begin{algorithmic}[1]
+        \REQUIRE $G=(V,E), S\subseteq V$
+        \IF{$|S|=1$}
+            \RETURN $0$ \COMMENT{\autoref{lem:helper-1}}
+        \ELSIF{$|S|=2$}
+            \IF{$e(s_1,s_2)$}
+                \RETURN $0$ \COMMENT{\autoref{lem:helper-2-edge}}
+            \ELSE
+                \RETURN $2+\ms(G\ex\iN(s_1)\ex\iN(s_2))$ \COMMENT{\autoref{lem:helper-2-noedge}}
+            \ENDIF
+        \ELSIF{$|S|=3$}
+            \IF{$\exists_i[d(s_i)=0]$}
+                \RETURN $1+\ms^1(G\ex s_i,S\ex s_i)$ \COMMENT{Special case of \autoref{lem:components}}
+            \ELSIF{$s_1,s_2,s_3$ form a three-cycle}
+                \RETURN $0$ \COMMENT{Impossible to pick two vertices from a three-cycle}
+            \ELSIF{$\exists_{i,j,k}[i\neq k \land e(s_i,s_j) \land e(s_i,s_k)]$}
+                \RETURN $2 + \ms(G\ex\iN(s_j)\ex\iN(s_k))$ \COMMENT{Impossible to choose $s_i$ and another vertex, so we have to choose $s_j$ and $s_k$}
+            \ELSIF{$\exists_{i,j}[e(s_i,s_j)]$}
+                \STATE $s_k\gets S\ex s_1\ex s_j$
+                \RETURN $1 + \ms^1(G\ex\iN(s_k), S\ex s_k)$ \COMMENT{Impossible to choose $s_i$ and $s_j$, so we choose $s_k$ and one of $s_i,s_j$}
+            \ELSIF{$\exists_{i,j}[N(s_i)\cap N(s_j)\neq\emptyset]$}
+                \RETURN $\ms^2(G\ex(N(s_i)\cap N(s_j)), S)$ \COMMENT{m.i.s. contains either $s_i$ or $s_j$, so not their common neighbours}
+            \ELSIF{$\exists_i[d(s_i)=1]$}
+                \RETURN $1+\ms^1(G\ex\iN(s_i),S\ex s_i)$ \COMMENT{Special case of \autoref{lem:one-neighbour}}
+            \ELSE
+                \RETURN $\max(1+\ms^1(G\ex\iN(s_1),S\ex s_1), 2 + \ms^2(G\ex\iN(s_2)\ex\iN(s_3)\ex s_1, N(s_1)))$ \COMMENT{Either the m.i.s. does contain $s_1$, and one of $s_2,s_3$, or it doesn't. In the latter case, it must contain $s_2,s_3$, and at least two on $s_1$'s neighbours, using an argument similar to \autoref{lem:two-neighbours}. Robson misses the `$2+$' for this second case, but from the writing it is clear that it should be included.}
+            \ENDIF
+        \ELSIF{$|S|=4$}
+            \IF{$\lnot\exists_i[d(s_i)\leq3]$}
+                \RETURN $\max(1+\ms(G\ex\iN(s_1)),\ms^2(G\ex s_1,S\ex s_1))$ \COMMENT{m.i.s. either does or doesn't contain $s_1$}
+            \ELSE
+            \RETURN $\ms(G)$ \COMMENT{More efficient than the $\max$ in this case; \autoref{lem:helper-general}}
+            \ENDIF
+        \ELSE
+            \RETURN $\ms(G)$ \COMMENT{No clever optimisation found; \autoref{lem:helper-general}}
+        \ENDIF
+    \end{algorithmic}
+\end{algorithm}
+
+\bigskip
+
+As the observant reader may have noticed, we use $\ms^1$ in the definition of $\ms^2$. We therefore also need to write an efficient algorithm to apply this function. Of course, \autoref{lem:helper-general} and \ref{lem:helper-1} apply to $\ms^1$ as well. Note, that we always call $\ms^1(\cdots,S)$ with $|S|=2$. We will therefore not give a complete algorithm $\ms^1$, but one that works in the necessary cases.
+
+\begin{lemmaproof}[helper-intersection]{If $N(s_1)\cap N(s_2)\neq\emptyset$, we know $\ms^1(G,S)=\ms^1(G\ex(N(s_1)\cap N(s_2)), S)$.}
+    This was already used in \autoref{alg:ms2}, in the case of three states. The m.i.s. will contain either $s_1$ or $s_2$, therefore cannot contain the intersection of their neighbourhoods. Removing these vertices allows for early pruning.
+\end{lemmaproof}
+
+Robson adds further optimisations to this.
+
+\begin{lemmaproof}[helper-ms1-2-2]{If $d(s_1)=d(s_2)=2$ and $\lnot e(s_1,s_2)$, an m.i.s. containing one of $s_1,s_2$ will contain either $s_1$ or $N(s_1)\with\{s_2\}$.}
+    In the case that the m.i.s. contains $s_1$, we are done. If an m.i.s. $ms$ does not contain $s_1$ but $s_2$, it must contain $N(s_1)$, because otherwise $ms\ex N(s_1)\with s_1$ is an independent set of at least the same size.
+\end{lemmaproof}
+
+If the conditions of \autoref{lem:helper-ms1-2-2} are met, write $w_1,w_2$ for the two neighbours of $s_1$.
+
+\begin{lemmaproof}[helper-ms1-2-2-edge]{If the conditions of \autoref{lem:helper-ms1-2-2} are met and $e(w_1,w_2)$, we have $\ms^1(G,S)=1+\ms(G\ex s_1)$.}
+    It cannot be the case that an m.i.s. will contain $N(s_1)$. \autoref{lem:helper-ms1-2-2} leaves this (choosing $s_1$) as only option.
+\end{lemmaproof}
+
+\begin{lemmaproof}[helper-ms1-2-2-dominance]{If the conditions of \autoref{lem:helper-ms1-2-2} are met and $N^2(s_1)\subset N(s_2)$, we have $\ms^1(G,S)=3+\ms(G\ex\iN(s_1)\ex\iN(s_2))$.}
+    Obviously, an m.i.s. $\iN(s_1)+\iN(s_2)$ that contains $s_1$ or $s_2$ cannot be larger than three. Furthermore, $\{w_1,w_2,s_2\}$ is an independent set and dominates every other independent set of the same size.
+\end{lemmaproof}
+
+This leads us to a slightly adapted version of $\ms^2$ that we can use for $\ms^1$. Pseudocode is given in \autoref{alg:ms1}.
+
+\begin{algorithm}[h]
+    \caption{Finding the size of the m.i.s. of a graph, given that it should contain one node from a certain subgraph}
+    \label{alg:ms1}
+    \begin{algorithmic}[1]
+        \REQUIRE $G=(V,E), S\subseteq V, d(s_1)\leq d(s_2)$
+        \IF{$d(s_1)\leq1$}
+            \RETURN $\ms(G)$ \COMMENT{\autoref{lem:helper-general}} \label{alg:ms1:case-d1}
+        \ELSIF{$e(s_1,s_2)$}
+            \IF{$d(s_1)>3$}
+                \RETURN $1 + \max(\ms(G\ex\iN(s_1)), \ms(G\ex\iN(s_2)))$ \COMMENT{An m.i.s. contains either $s_1$ or $s_2$, but not both} \label{alg:ms1:case-edge-d4}
+            \ELSE
+                \RETURN $\ms(G)$ \COMMENT{More efficient than the $\max$ in this case; \autoref{lem:helper-general}}\label{alg:ms1:case-edge-d3}
+            \ENDIF
+        \ELSIF{$N(s_1)\cap N(s_2)\neq\emptyset$}
+            \RETURN $\ms^1(G\ex(N(s_1)\cap N(s_2)), S)$ \COMMENT{m.i.s. contains $s_1$ or $s_2$, so not their common neighbours}\label{alg:ms1:intersection}
+        \ELSIF{$d(s_1)=d(s_2)=2$}
+            \STATE $\{w_1,w_2\} \gets N(s_1)$
+            \IF{$e(w_1,w_2)$}
+                \RETURN $1+\ms(G\ex\iN(s_1))$ \COMMENT{\autoref{lem:helper-ms1-2-2-edge}}\label{alg:ms1:case-2-2-edge}
+            \ELSIF{$N^2(s_1)\subset N(s_2)$}
+                \RETURN $3 + \ms(G\ex\iN(s_1)\ex\iN(s_2))$ \COMMENT{\autoref{lem:helper-ms1-2-2-dominance}}\label{alg:ms1:case-2-2-dominance}
+            \ELSE
+                \RETURN $\max(1+\ms(G\ex\iN(s_1)), 3+\ms(G\ex\iN(w_1)\ex\iN(w_2)\ex\iN(s_2)))$ \COMMENT{\autoref{lem:helper-ms1-2-2}}\label{alg:ms1:case-2-2-else}
+            \ENDIF
+        \ELSE
+            \RETURN $1+\max(\ms(G\ex\iN(s_2)), \ms^2(G\ex\iN(s_1)\ex s_2, N(s_2)))$ \COMMENT{An m.i.s. contains either $s_2$ or $s_1$ and two of $s_2$'s neighbours. If an m.i.s. $ms$ would contain $s_1$ and at most one of $s_2$'s neighbours, say $w$, then there is another independent set $ms\ex w\with s_2$, which is at least as large.}\label{alg:ms1:case-general}
+        \ENDIF
+    \end{algorithmic}
+\end{algorithm}
+
diff --git a/Practical1/report/analysis.tex b/Practical1/report/analysis.tex
new file mode 100644
index 0000000..4174e87
--- /dev/null
+++ b/Practical1/report/analysis.tex
@@ -0,0 +1,54 @@
+\section{Complexity analysis}
+\label{sec:analysis}
+
+Robson provides us with a very detailed analysis proving that the $\ms$ algorithm runs in $\pazocal O(\mathrm{polynomial}(n)\cdot2^{cn})$, where $c<0.296$ and with $n$ the number of vertices of the input graph \cite{robson}. However, the argument is over my head, so I will provide my own, simpler, less exact analysis here.
+
+We write $T_{\ms}(n)$ for the running time of $\ms$ on a graph $G$ with $|G|=n$. For $\ms^n$ we write $T_{\ms^n}(p,q)$ for the appliance of $\ms^n$ on a graph $G$ with $|G|=p$ and a set $S$ to pick $n$ vertices from with $|S|=q$. In the case of $n=1$, we write $T_{\ms^1}(p)$ instead of $T_{\ms^1}(p,2)$, because we only use the case of $q=2$.
+
+\subsection{$\ms^1$: \autoref{alg:ms1}}
+\label{sec:analysis:ms1}
+
+This function is a simple case distinction. Let's therefore consider the complexities of all the cases one by one. The results, along with their line numbers in \autoref{alg:ms1}, may be found in \autoref{tab:analysis:ms1}.
+
+\begin{table}[h]
+    \centering
+    \renewcommand{\arraystretch}{1.3}
+    \begin{tabular}{l | p{29mm} | p{19mm} | p{50mm}}
+        Ln. & Case & Complexity & Argumentation \\\hline\hline
+        \ref{alg:ms1:case-d1}       & $d(s_1)\leq 1$
+            & $T_{\ms}(n-1)$
+            & Simple recurrence \\\hline
+        \ref{alg:ms1:case-edge-d4} & $e(s_1,s_2), d(s_1)>3$
+            & $2T_{\ms}(n-5)$
+            & Both vertices have degree four, so we run $\ms$ twice on a graph with five vertices less\\\hline
+        \ref{alg:ms1:case-edge-d3} & $e(s_1,s_2), d(s_1)\leq3$
+            & $T_{\ms}(n)$
+            & Simple recurrence \\\hline
+        \ref{alg:ms1:intersection} & $N(s_1)\cap N(s_2)\neq\emptyset$
+            & $T_{\ms^1}(n-1)$ 
+            & At least one vertex removed \\\hline
+        \ref{alg:ms1:case-2-2-edge} & $d(s_1)=d(s_2)=2$, $e(w_1,w_2)$
+            & $T_{\ms}(n-3)$
+            & Simple recurrence \\\hline
+        \ref{alg:ms1:case-2-2-dominance} & $d(s_1)=d(s_2)=2$, $N^2(s_1)\subset N(s_2)$
+            & $T_{\ms}(n-6)$
+            & Exactly six vertices removed \\\hline
+        \ref{alg:ms1:case-2-2-else} & $d(s_1)=d(s_2)=2$, otherwise
+            & $T_{\ms}(n-3) + T_{\ms}(n-7)$ 
+            & In the first case three vertices removed, in the second case seven \\\hline
+        \ref{alg:ms1:case-general} & Otherwise
+            & $T_{\ms}(n-3) + T_{\ms^2}(n-4,4)$
+            & In the first case at least three vertices removed, in the second case four, and at most four to choose two from
+    \end{tabular}
+    \caption{Worst-case complexity analysis of the different cases of $\ms^1$}
+    \label{tab:analysis-ms1}
+\end{table}
+
+\subsection{$\ms^2$: \autoref{alg:ms2}}
+\label{sec:analysis:ms2}
+%todo
+
+\subsection{$\ms$: \autoref{alg:ms}}
+\label{sec:analysis:ms}
+%todo
+
diff --git a/Practical1/report/implementation.tex b/Practical1/report/implementation.tex
new file mode 100644
index 0000000..5c6bbff
--- /dev/null
+++ b/Practical1/report/implementation.tex
@@ -0,0 +1,84 @@
+\section{Implementing the algorithm}
+\label{sec:implementation}
+
+A Java application accompanies this report. I have chosen for a simple implementation of a vertex:
+
+\begin{minted}[fontsize=\footnotesize,linenos,breaklines,tabsize=0]{java}
+	class Node<T> implements Comparable<Node<T>> {
+	    private final T content;
+	    private final List<Node<T>> neighbours = new ArrayList<>();
+	
+	    public Node(T content);
+	
+	    public int getDegree();
+	    public List<Node<T>> getNeigbourhood();
+	    public List<Node<T>> getInclusiveNeighbourhood();
+	    public List<Node<T>> getSecondNeighbourhood();
+	
+	    public boolean dominates(Node<T> b);
+	    public boolean neighbourhoodsDisjoint(Node<T> b);
+	    public List<Node<T>> neighbourhoodIntersection(Node<T> b);
+	
+	    public String toString();
+	    public boolean equals(Object b);
+	    public int compareTo(Node<T> b);
+	}
+\end{minted}
+
+The \texttt{Node} class implements \texttt{Comparable<Node<T>>} to be able to sort on degree.
+
+We only consider vertices with degree between $0$ and $4$ in this problem. Therefore, we may consider all these methods to run in constant time. Most of the methods run already in constant time. Some need to iterate over the list of neighbours (and possibly their neighbours), but if the degrees of all vertices is between $0$ and $4$ we're talking about at most $16$ vertices, which we can consider constant.
+
+The data structure of a graph is even simpler. It is implemented as a list of nodes. But some of the functions that we used in the algorithms in \autoref{sec:algorithm} above, give us a problem. Whenever $\max()$ is used in the algorithms, we consider different possibilities, which need to be investigated separately.
+
+At first, I wrote a program that created a new graph for every recurrence, and then ran the $\ms$, $\ms^2$ or $\ms^1$ algorithm on that new graph. This approach has the advantage that it allows for multi-threading. Letting the graph class implement \texttt{Runnable} we can run different cases in different threads, taking the $\max()$ of their results when they finish. However, it turned out that copying the list of a graph's nodes \emph{leaving the references to each other intact} caused a lot of overhead, making it in practice an unusable approach.
+
+The other approach is to, when investigating a subgraph, make some modifications to the graph object itself, running $\ms$ or $\ms^n$ on the same object, and reverting the modifications before moving on to the next case. This is slightly more difficult to implement, but has the big advantage of not needing exponential space. Also, it turned out to be faster in practice, as said above.
+
+The graph therefore has a stack of lists of nodes as a private member. Every element on the stack is a restore point. There is a method to create a new restore point, which pushes an empty list to the stack. Whenever nodes are removed from the graph, they are added to the element at the top of the stack. Lastly, there is a method that pops the first element of the stack, restores the nodes in that list, putting them back in the graph.
+
+That gives us the signature of the \texttt{Graph} class:
+
+\begin{minted}[fontsize=\footnotesize,linenos,breaklines,tabsize=0]{java}
+	class Graph<T> {
+	    private final List<Node<T>> nodes;
+	    private final Stack<List<Node<T>>> restorePoints = new Stack<>();
+	    
+	    public Graph();
+	    public Graph(List<Node<T>> nodes);
+	
+	    public int maximumIndependentSetSize();
+	    private int maximumIndependentSetSizeWith1From(Node<T> s_1, Node<T> s_2);
+	    private int maximumIndependentSetSizeWith2From(Collection<Node<T>> Scol);
+	
+	    private Graph<T> findStronglyConnectedComponent();
+	    
+	    public void addNode(Node<T> node);
+	    public Node<T> getNode(int i);
+	    private void removeNode(Node<T> node);
+	    private void removeNodes(Collection<Node<T>> ns);
+	
+	    private void restorePoint();
+	    private void restore();
+	
+	    public int size();
+	    public String toString();
+	}
+\end{minted}
+
+Only the method \texttt{findStronglyConnectedComponent} creates a new \texttt{Graph} object. We are talking about graphs of up to $100$ vertices, so we will create at most $100$ \texttt{Graph} objects, which is acceptable.
+
+The \texttt{removeNode}(\texttt{s}) methods don't only remove their argument(s) from the graph, they also remove the references to their arguments from any node that is still in the graph. But because this means removing at most $4$ references per node removed, this runs in linear time relative to the number of nodes to be removed.
+
+The \texttt{addNode} and \texttt{getNode} methods are simply wrappers for the \texttt{nodes} member, which run in constant time, as do \texttt{size}, \texttt{toString} and \texttt{restorePoint}. The \texttt{restore} method needs to add earlier removed nodes (say $n$) back to the graph, and add their references back to their neighbours. However, since every node has at most $4$ neighbours, this runs in linear time relative to the number of nodes to restore.
+
+Using these two classes in the problem at hand turns out to be as simple as:
+
+\begin{minted}[fontsize=\footnotesize,linenos,breaklines,tabsize=0]{java}
+	Graph graph = new Graph<Integer>();
+	int n_bins = readGraph(new Scanner(System.in), graph);
+	System.out.println(graph.maximumIndependentSetSize() >= n_bins ? "possible" : "impossible");
+\end{minted}
+
+A suitable implementation of \texttt{readGraph} is outside the scope of this report.
+
diff --git a/Practical1/report/notation.tex b/Practical1/report/notation.tex
new file mode 100644
index 0000000..3458029
--- /dev/null
+++ b/Practical1/report/notation.tex
@@ -0,0 +1,7 @@
+\section{Notation}
+I'm largely following Robson's notation \cite{robson}. For a graph $G=(V,E)$ and vertex $v\in V$, and edge $e\in E$, we write $d(v)$ for the degree of the vertex. $N(v)$ is the set of $v$'s neighbours, and $\iN(v)=N(v)\cup\{v\}$, $v$'s `inclusive neighbourhood'. Then $N^2(v)$ is the set of second order neighbours of $v$, excluding $v$: $N^2(v)=\{v_2 \in N(v_1) \mid v_1\in N(v)\} \setminus \{v\}$. If $\iN(v)\subseteq\iN(w)$, $v$ is said to dominate $w$, notation: $v>w$.
+
+We write `subgraph' for `vertex-induced subgraph', and $G\ex U$ for the subgraph induced on $G$ by $U$. For $v\in V$, we write $G\ex v$ for $G\ex\{v\}$. We use $e(v,w)$ for the predicate $(v,w)\in E$. We're strictly talking about non-directed graphs, so this is equivalent with $(w,v)\in E$.
+
+Finally, We write `m.i.s.' for `maximum independent set' and $\ms(\cdots)$ for its size, the graph's independence number. The size of a graph or an m.i.s. is defined as the number of vertices and is written as $|G|$.
+
diff --git a/Practical1/report/report.tex b/Practical1/report/report.tex
new file mode 100644
index 0000000..9ce7df9
--- /dev/null
+++ b/Practical1/report/report.tex
@@ -0,0 +1,81 @@
+\documentclass[10pt,a4paper]{article}
+
+% textcomp package is not available everywhere, and we only need the Copyright symbol
+% taken from http://tex.stackexchange.com/a/1677/23992
+\DeclareTextCommandDefault{\textregistered}{\textcircled{\check@mathfonts\fontsize\sf@size\z@\math@fontsfalse\selectfont R}}
+
+\usepackage{fancyhdr}
+\renewcommand{\headrulewidth}{0pt}
+\renewcommand{\footrulewidth}{0pt}
+\fancyhead{}
+%\fancyfoot[C]{Copyright {\textcopyright} 2015 Camil Staps}
+\pagestyle{fancy}
+
+\usepackage{amsmath}
+\usepackage{amsthm}
+\usepackage{amsfonts}
+\DeclareMathAlphabet{\pazocal}{OMS}{zplm}{m}{n}
+
+\usepackage[hidelinks]{hyperref}
+\usepackage{url}
+
+\newcommand*\iN{\bar{N}}
+\newcommand*\ex{-}
+\newcommand*\with{+}
+\DeclareMathOperator{\ms}{\alpha}
+
+\providecommand*{\lemmaautorefname}{Lemma}
+\newtheorem{lemma}{Lemma}
+
+\newenvironment{lemmaproof}[2][]{%
+    \begin{lemma}%
+        \def\temp{#1}\ifx\temp\empty\else\label{lem:#1}\fi%
+        #2%
+    \end{lemma}%
+    \begin{proof}%
+}{\end{proof}}
+
+\newcommand{\refeq}[2][]{\begin{equation}\label{eq:#1}#2\end{equation}}
+
+\numberwithin{lemma}{subsection}
+
+\usepackage{algorithm}
+\usepackage{algorithmic}
+\providecommand*{\algorithmautorefname}{Algorithm}
+
+\usepackage{minted}
+
+\title{Miss Algorithm}
+\author{Camil Staps\\\small{s4498062}}
+
+\begin{document}
+
+\maketitle
+\thispagestyle{fancy}
+
+\begin{abstract}
+    No, this report is not about a new beauty pageant. It is about the realisation and implementation of a maximum independent set size (miss) algorithm.
+
+    Garbage collectors and the local government of Nijmegen have agreed to place garbage bins on the at most 100 intersections of the at most 200 streets of the city, with the restriction that no two neighbouring intersections may both have a garbage bin. In this report we will discuss an algorithm that can check whether $k$ garbage bins can be placed following that rule.
+
+    This problem is of course a fancy formulation of the maximum independent set problem. So to answer the question, we implement an algorithm that computes the size of the maximum independent set, and verify if $k$ is small enough.
+\end{abstract}
+
+\section{Report organisation}
+%todo
+
+\input{notation}
+\input{algorithm}
+\input{implementation}
+\input{analysis}
+
+\section{Acknowledgements}
+\label{sec:acknowledgements}
+I'm grateful to Tom van der Zanden for pointing me to the term `maximum independent set', which eventually let me to Robson's algorithm \cite{robson}.
+
+\begin{thebibliography}{9}
+    \bibitem{robson}{Robson, J.M. (1985). \emph{Algorithms for Maximum Independent Sets}.}
+\end{thebibliography}
+
+\end{document}
+