\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 time complexity analysis of the different cases in \autoref{alg:ms1}}
    \label{tab:analysis-ms1}
\end{table}

\subsection{$\ms^2$: \autoref{alg:ms2}}
\label{sec:analysis:ms2}
Also this is a simple case distinction. Let's again put the different cases in a table, along with their line numbers. See \autoref{tab:analysis-ms2}.

\begin{table}[h]
    \centering
    \renewcommand{\arraystretch}{1.3}
    \begin{tabular}{l | p{29mm} | p{19mm} | p{50mm}}
        Ln. & Case & Complexity & Argumentation \\\hline\hline
    \end{tabular}
    \caption{Worst-case time complexity analysis of the different cases in \autoref{alg:ms2}}
    \label{tab:analysis-ms2}
\end{table}

%todo

\subsection{$\ms$: \autoref{alg:ms}}
\label{sec:analysis:ms}
%todo