1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
\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
|
