<commit_before>\documentclass{article}

\usepackage{placeins}

\begin{document}

\begin{titlepage}
		\noindent{\huge Minimum Fill-In} \\ \\
		<NAME>, \\ <NAME>, \\ \& <NAME>	\\ \\
		\hspace{-18pt}
		\textit{June 2, 2017}
		\thispagestyle{empty}
		\vspace{\fill}
		\section*{Abstract}
		This article describes the implementation of the fixed-parameter algorithm for solving the minimum fill-in problem by Bodlaender et al. in \cite{algorithm} in C++. Concrete solutions for each subproblem in the algorithm is described and several optimizations are explored, with varying success.
	\end{titlepage}
	\clearpage

	\section{Algorithm}
	The algorithm\cite{algorithm} is concerned with finding four-cycles and certain substructures in the graph, called moplexes, which are defined as adhering to the following rules: \\

	\begin{description}
		\item[Clique] Every vertex in the moplex must be connected to all other vertices.
		\item[Shared neighborhood] Every vertex in the moplex must have the same neighborhood.
		\item[Minimal separator neighborhood] The neighborhood of the moplex is a minimal separator, meaning that if the neighborhood is removed from the graph, the graph is split into multiple parts. Removal of any proper subset of the neighborhood must not split the graph, hence it is minimal.
		\item[Maximally inclusive] If a vertex can be added to a moplex, without it not being a moplex anymore, that vertex must be included.
	\end{description}

	Furthermore, simplicial moplexes are moplexes where the neighborhood of the moplex is also a clique.

	As an indicator that an edge will at some point need to be connected to another vertex, \emph{markings} are used in this algorithm. 
	A maximum of two times k markings are allowed, where k is the number of fill edges in the decision problem.

		\subsection{Kernelization}
		The kernelization algorithm used, described in \cite{kernel}, is split into three phases. Even though the kernelization algorithm is fixed-parameter tractable, it turns out that Phase 1 and 2 can be run with $k=\infty$, and only Phase 3 needs a fixed-parameter $k$, see \cite{polynomial-approx}. The kernelization produces a set of vertices which might be relevant to the minimum fill-in algorithm, set $A$, a set of vertices which are definitely not relevant, set $B$, and a set of essential edges which must be part of a solution to the minimum fill-in problem, if one exists of size $k$. 

		The three phases are:
		\begin{description}
			\item[Phase 1] finds independent chordless cycles in the graph, by utilizing the fact that non-chordal graphs do not have a perfect elimination order (PEO). After a chordless cycle is found, it is removed from the graph, in order to ensure that it is independent from the other chordless cycles found. The vertices in the chordless cycles are added to set $A$, and removed from set $B$.
			\item[Phase 2] finds chordless cycles which share one or more vertices with another cycle. It uses the sets $A$ and $B$ produced by Phase 1, to find cycles that have vertices in both sets. As in phase 1, the vertices in cycles are added to $A$ and removed from $B$.
			\item[Phase 3] finds essential edges for a solution of size $k$, by evaluating all non-edges in the graph. If it finds a non-essential non-edge in a chordless cycle not containing an essential edge, it adds all the vertices of the cycle to $A$ and removes them from $B$, thus ensuring that all chordless cycles are present in $A$.
		\end{description}

		\subsection{Cases} 
		Once the graph has been kernelized, the algorithm is called with an initial k-value. The algorithm then tries to find a solution for the graph with the initial k-value.
		If no solution with the given k-value can be found, $k$ is incremented and the algorithm is run again.
		The algorithm is recursively called with a the k-value and in each iteration the first of six actions are performed, where the criteria of that case is met.
		These cases are, in order:
		\begin{description}
			\item[Four-cycle] If a four-cycle exists, the program branches on both possible resolutions of the four-cycle.
			\item[Moplex with marked and unmarked vertices] If a moplex containing marked and unmarked vertices exists in the graph, all vertices of the moplex are marked.
			\item[Simplicial moplex with only unmarked edges] If \emph{any} simplicial moplexes containing only unmarked edges, exist in the graph, they are removed.
			\item[Unmarked moplex with a neighborhood missing only one edge] If a moplex containing only unmarked vertices and which has a neighborhood that is only missing one edge in order to be a clique, exists, the missing edge is added. In this case if a marked vertex, called $v_{star}$ fulfilling specific criteria is found, it is unmarked.
			\item[Only marked moplexes] If all moplexes in the graph are marked, no solution with the given k-value exists.
			\item[Any unmarked moplex] If there are any unmarked moplexes in the graph, the program branches into two. In the first branch, every vertex in the moplex is marked. In the other branch, every edge missing in the neighborhood of the moplex is added.
		\end{description}

		At the start of each iteration, the graph is checked for chordality and if k has reached zero, the algorithm increments k and starts over.

	\section{Implementation challenges}
	As the concrete solutions for each subproblem within the algorithm are unexplored in the original article, they are not trivially solved optimally.

		\subsection{Data structure}
		To efficiently store the graph in memory an adjacency list is used.
		In practice this is implemented as a vector of binary search tree sets.
		While asserting whether or not two vertices share an edge, is possible in constant time using hash sets, the size of the edge sets are generally not large enough to outweigh the ability to compare sets.

		Other graph representations, like the adjacency matrix, were attempted, but as the algorithm relies heavily on iterating over vertex neighborhoods, the less efficient edge list access worsened the overall efficiency of the algorithm severely.

		\subsection{Chordality}

		\subsection{Four-cycles}
		As the algorithm branches on chordal completions of four-cycles, an efficient approach to finding these in the graph is needed.
		It must be possible to either find one four-cycle or report that none exist.
		This is accomplished using a depth-first search to a maximum depth of four, checking for lesser cycles along the way.
		If no lesser cycles are present and the starting vertex is found at a depth of four, a four-cycle is reported.
		If no four-cycles are found starting the search in every vertex of the graph, none are present in the graph.
		The time complexity of this approach is $O(VE^4)$ as it is potentially necessary to check every edge in the graph in all four depths for every vertex.

		Yuster and Zwick\cite{finding-even-cycles} describes an algorithm to detect four-cycles in $O(n^2)$ time, but requiring $O(n)$ extra space.
		The algorithm uses an empty adjacency matrix the size of the graph and turns the neighborhood of each vertex in the original graph into a clique in the matrix.
		If an edge is added to the matrix twice, a four-cycle is present and can be extracted in linear time.
		This algorithm was attempted in the C\# prototype but turned out to be much slower than depth-first search, likely due to the memory overhead.
		With an optimal implementation, perhaps using bit-vectors and the AVX instruction set, this algorithm might be worthwhile, but time constraints prevented such attempts.

		\subsection{Moplexes}

		\subsection{V-star}
		$v_{star}$ is defined as the second to last vertex on each path between the two vertices, $x$ and $y$, which are missing an edge, as described in the case.
		In order to find a potential $v_{star}$, a breadth-first search is run from $x$ and for each vertex a node is created and added to a linked-list, which will branch out once the paths start to diverge.
		Once $y$ is added to the path, it is checked for chords.
		Once all paths are found, the second to last node is compared for each path, first from $x$ to $y$, then from $y$ to $x$.
		The complexity of this algorithm is $O(n^2)$, due to the check for chordlessness inside the BFS.

	\section{Optimizations}
	The algorithm has been implemented in C++ to allow for greater optimization.

		\subsection{Moplex caching}
		A very large part of the algorithm is in locating every moplex in the graph, since this is used in every case of the algorithm, excluding the case where a four-cycle is found.
		Because the moplexes change fairly little in each iteration of the algorithm, these are cached in order to reduce the amount of time wasted on finding already found moplexes.

		It is accomplished by keeping track of which moplexes were found in the last iteration and which of these might have been effected by a change in the graph.

		\subsection{Component splitting}
		Since the graph is possibly divided into smaller kernels by the kernelization algorithm, the problem can potentially reduced to several instances with a lower k each, the performance of the program should greatly increase.

		This is accomplished by running the core of the algorithm on each found component of the graph, with an initial k-value of 0, or the k returned by the kernelization, if only one component exists in the graph.

		\subsection{Subgraphs}
		Many functions used by the algorithm requires subgraphs to be considered, such as the kernelization and the deletion of simplicial moplexes.
		Since the algorithm is depth-first, meaning each branch is explored exhaustively before the next branch is considered, the changes made must be easily reversible.<commit_msg>correction<commit_after>\documentclass{article}

\usepackage{placeins}

\begin{document}

\begin{titlepage}
		\noindent{\huge Minimum Fill-In} \\ \\
		<NAME>, \\ <NAME>, \\ \& <NAME>	\\ \\
		\hspace{-18pt}
		\textit{June 2, 2017}
		\thispagestyle{empty}
		\vspace{\fill}
		\section*{Abstract}
		This article describes the implementation of the fixed-parameter algorithm for solving the minimum fill-in problem by Bodlaender et al. in \cite{algorithm} in C++. Concrete solutions for each subproblem in the algorithm is described and several optimizations are explored, with varying success.
	\end{titlepage}
	\clearpage

	\section{Algorithm}
	The algorithm\cite{algorithm} is concerned with finding four-cycles and certain substructures in the graph, called moplexes, which are defined as adhering to the following rules: \\

	\begin{description}
		\item[Clique] Every vertex in the moplex must be connected to all other vertices.
		\item[Shared neighborhood] Every vertex in the moplex must have the same neighborhood.
		\item[Minimal separator neighborhood] The neighborhood of the moplex is a minimal separator, meaning that if the neighborhood is removed from the graph, the graph is split into multiple parts. Removal of any proper subset of the neighborhood must not split the graph, hence it is minimal.
		\item[Maximally inclusive] If a vertex can be added to a moplex, without it not being a moplex anymore, that vertex must be included.
	\end{description}

	Furthermore, simplicial moplexes are moplexes where the neighborhood of the moplex is also a clique.

	As an indicator that an edge will at some point need to be connected to another vertex, \emph{markings} are used in this algorithm. 
	A maximum of two times k markings are allowed, where k is the number of fill edges in the decision problem.

		\subsection{Kernelization}
		The kernelization algorithm used, described in \cite{kernel}, is split into three phases. Even though the kernelization algorithm is fixed-parameter tractable, it turns out that Phase 1 and 2 can be run with $k=\infty$, and only Phase 3 needs a fixed-parameter $k$, see \cite{polynomial-approx}. The kernelization produces a set of vertices which might be relevant to the minimum fill-in algorithm, set $A$, a set of vertices which are definitely not relevant, set $B$, and a set of essential edges which must be part of a solution to the minimum fill-in problem, if one exists of size $k$. 

		The three phases are:
		\begin{description}
			\item[Phase 1] finds independent chordless cycles in the graph, by utilizing the fact that non-chordal graphs do not have a perfect elimination order (PEO). After a chordless cycle is found, it is removed from the graph, in order to ensure that it is independent from the other chordless cycles found. The vertices in the chordless cycles are added to set $A$, and removed from set $B$.
			\item[Phase 2] finds chordless cycles which share one or more vertices with another cycle. It uses the sets $A$ and $B$ produced by Phase 1, to find cycles that have vertices in both sets. As in phase 1, the vertices in cycles are added to $A$ and removed from $B$.
			\item[Phase 3] finds essential edges for a solution of size $k$, by evaluating all non-edges in the graph. If it finds a non-essential non-edge in a chordless cycle not containing an essential edge, it adds all the vertices of the cycle to $A$ and removes them from $B$, thus ensuring that all chordless cycles are present in $A$.
		\end{description}

		\subsection{Cases} 
		Once the graph has been kernelized, the algorithm is called with an initial k-value. The algorithm then tries to find a solution for the graph with the initial k-value.
		If no solution with the given k-value can be found, $k$ is incremented and the algorithm is run again.
		The algorithm is recursively called with a the k-value and in each iteration the first of six actions are performed, where the criteria of that case is met.
		These cases are, in order:
		\begin{description}
			\item[Four-cycle] If a four-cycle exists, the program branches on both possible resolutions of the four-cycle.
			\item[Moplex with marked and unmarked vertices] If a moplex containing marked and unmarked vertices exists in the graph, all vertices of the moplex are marked.
			\item[Simplicial moplex with only unmarked edges] If \emph{any} simplicial moplexes containing only unmarked edges, exist in the graph, they are removed.
			\item[Unmarked moplex with a neighborhood missing only one edge] If a moplex containing only unmarked vertices and which has a neighborhood that is only missing one edge in order to be a clique, exists, the missing edge is added. In this case if a marked vertex, called $v_{star}$ fulfilling specific criteria is found, it is unmarked.
			\item[Only marked moplexes] If all moplexes in the graph are marked, no solution with the given k-value exists.
			\item[Any unmarked moplex] If there are any unmarked moplexes in the graph, the program branches into two. In the first branch, every vertex in the moplex is marked. In the other branch, every edge missing in the neighborhood of the moplex is added.
		\end{description}

		At the start of each iteration, the graph is checked for chordality and if k has reached zero, the algorithm increments k and starts over.

	\section{Implementation challenges}
	As the concrete solutions for each subproblem within the algorithm are unexplored in the original article, they are not trivially solved optimally.

		\subsection{Data structure}
		To efficiently store the graph in memory an adjacency list is used.
		In practice this is implemented as a vector of binary search tree sets.
		While asserting whether or not two vertices share an edge, is possible in constant time using hash sets, the size of the edge sets are generally not large enough to outweigh the ability to compare sets.

		Other graph representations, like the adjacency matrix, were attempted, but as the algorithm relies heavily on iterating over vertex neighborhoods, the less efficient edge list access worsened the overall efficiency of the algorithm severely.

		\subsection{Chordality}

		\subsection{Four-cycles}
		As the algorithm branches on chordal completions of four-cycles, an efficient approach to finding these in the graph is needed.
		It must be possible to either find one four-cycle or report that none exist.
		This is accomplished using a depth-first search to a maximum depth of four, checking for lesser cycles along the way.
		If no lesser cycles are present and the starting vertex is found at a depth of four, a four-cycle is reported.
		If no four-cycles are found starting the search in every vertex of the graph, none are present in the graph.
		The time complexity of this approach is $O(VE^4)$ as it is potentially necessary to check every edge in the graph in all four depths for every vertex.

		Yuster and Zwick\cite{finding-even-cycles} describes an algorithm to detect four-cycles in $O(n^2)$ time, but requiring $O(n)$ extra space.
		The algorithm uses an empty adjacency matrix the size of the graph and turns the neighborhood of each vertex in the original graph into a clique in the matrix.
		If an edge is added to the matrix twice, a four-cycle is present and can be extracted in linear time.
		This algorithm was attempted in the C\# prototype but turned out to be much slower than depth-first search, likely due to the memory overhead.
		With an optimal implementation, perhaps using bit-vectors and the AVX instruction set, this algorithm might be worthwhile, but time constraints prevented such attempts.

		\subsection{Moplexes}

		\subsection{V-star}
		The vertex $v_{star}$ is defined as the second to last vertex on each path between the two vertices, $x$ and $y$, which are missing an edge, as described in the case.
		In order to find a potential $v_{star}$, a breadth-first search is run from $x$ and for each vertex a node is created and added to a linked-list, which will branch out once the paths start to diverge.
		Once $y$ is added to the path, it is checked for chords.
		Once all paths are found, the second to last node is compared for each path, first from $x$ to $y$, then from $y$ to $x$.
		The complexity of this algorithm is $O(n^2)$, due to the check for chordlessness inside the BFS.

	\section{Optimizations}
	The algorithm has been implemented in C++ to allow for greater optimization.

		\subsection{Moplex caching}
		A very large part of the algorithm is in locating every moplex in the graph, since this is used in every case of the algorithm, excluding the case where a four-cycle is found.
		Because the moplexes change fairly little in each iteration of the algorithm, these are cached in order to reduce the amount of time wasted on finding already found moplexes.

		It is accomplished by keeping track of which moplexes were found in the last iteration and which of these might have been effected by a change in the graph.

		\subsection{Component splitting}
		Since the graph is possibly divided into smaller kernels by the kernelization algorithm, the problem can potentially reduced to several instances with a lower k each, the performance of the program should greatly increase.

		This is accomplished by running the core of the algorithm on each found component of the graph, with an initial k-value of 0, or the k returned by the kernelization, if only one component exists in the graph.

		\subsection{Subgraphs}
		Many functions used by the algorithm requires subgraphs to be considered, such as the kernelization and the deletion of simplicial moplexes.
		Since the algorithm is depth-first, meaning each branch is explored exhaustively before the next branch is considered, the changes made must be easily reversible.
{'fraction_non_alphanumeric': 0.04763856162278455, 'fraction_numerical': 0.0019465218727589386, 'mean_word_length': 4.190906673756979, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '608323', 'n_tokens_mistral': 5131, 'n_tokens_neox': 4758, 'n_words': 3019}