\chapter{Algorithmic Toolbox}
\label{chapter2}
\markright{Mudabir Kabir Asathulla \hfill Chapter 2. Algorithmic Toolbox \hfill}
\paragraph{}
In this chapter, we introduce advanced data structures and algorithms that we will use in our algorithm. We give an overview of the Hopcroft-Karp algorithm and Lipton-Tarjan divide and conquer algorithm. We then provide details of $r$-division and $\textit{Dense Distance Graphs}$ which are used for construction of a compressed residual graph $H$ and for realizing faster implementations of the BFS and DFS in our algorithm. 

\section{ Hopcroft Karp Algorithm Revisited}
\label{HK revisited}
\paragraph{}
Our algorithm builds on top of the Hopcroft-Karp Algorithm \cite{hopcroft} and we provide a summary of the Hopcroft-Karp algorithm in this section. Introduced in 1973, this algorithm outperforms previous methods such as Edmonds \cite{edmonds} and Ford-Fulkerson algorithm \cite{ford} by finding a maximal set of shortest length vertex disjoint augmenting paths instead of just a single augmenting path per iteration. The pseudo code for Hopcroft-Karp Algorithm is shown in Algorithm \ref{alg:HK}.

\begin{algorithm}[H]
\caption{Hopcroft Karp algorithm}\label{alg:HK}
\begin{algorithmic}[1]
\Procedure{MaximumMatching}{$G(A\cup B,E$}
\State $M\gets \emptyset$
\While{Augmenting Path Exists}\Comment{Berge theorem \ref{th:berge}}
\State $l\gets$ length of shortest augmenting path
\State $P\gets \{P_1,P_2,\ldots,P_k\}$\Comment{$|P_i|=l$, $P$ is vertex disjoint}
\State $M\gets M \oplus (P_1 \cup P_2 \ldots \cup P_k)$
\EndWhile\label{endwhile}
\State \textbf{return} $M$\Comment{Maximum Matching}
\EndProcedure
\end{algorithmic}
\end{algorithm}
\paragraph{}
The shortest augmenting paths $\{P_1,P_2,\ldots,P_k\}$ are found using a combination of $\textit{breadth-first}$ $\textit{search}$ (BFS) and $\textit{depth-first-search}$ (DFS). Starting from free vertices of type $B$ in a partial matching, we perform BFS to construct a \textit{layered graph}. During the BFS search, each vertex being explored for the first time is added to the layered graph and is assigned a layer number indicating the length of the shortest path to that vertex from some free vertex of type $B$. Free vertices of type $B$ have layer number $0$. Layered graph comprises of free vertices of type $B$ and all vertices which are reachable from any free vertex of type $B$ with a distance less than or equal to the length of the shortest augmenting path. The BFS search terminates at the first layer where a free vertex of type $A$ is found or when all the vertices have been added. After constructing the layered graph, DFS is done to find a maximal set of augmenting paths and the algorithm increases the matching by one after augmenting each path. 
\begin{figure}[!ht]
\centering
\includegraphics[width=0.9\textwidth]{./images/Hopcroft.png}
\caption{Graph with partial matching and its layered graph}
\label{fig:hopcroft}
\end{figure}
\paragraph{}
The graph on the left in Figure \ref{fig:hopcroft} represents a partial matching with matched vertices shown uncolored and matched edges shown as thick lines. The layered graph for this partial matching is shown in right side of Figure \ref{fig:hopcroft}. The layered graph contains free vertices in the first and the last layers. All the vertices in the same column have the same layer number. Solid edges represent edges contributing to a maximal set of vertex disjoint augmenting paths while dashed edges are not part of a maximal set of augmenting paths in this iteration. BFS and DFS is repeated in each iteration till no augmenting paths are found.

Given a bipartite graph $G$ with $n$ vertices and $m$ edges, Hopcroft-Karp algorithm takes $O(m)$ time for BFS and DFS and as a consequence of finding maximal set of shortest length augmenting paths every iteration, the authors show that only $O(\sqrt{n})$ iterations are needed for the algorithm to terminate. 
\begin{lemma}
\label{lem:hopcroft}
The Hopcroft-Karp Algorithm runs in $O(m\sqrt{n})$ time.
\end{lemma}
\begin{proof}
We prove this lemma using the property of Hopcroft-Karp algorithm that the length of the augmenting path strictly increases every iteration. Since any augmenting path is always of odd length, the length increases by at least $2$ after each iteration. After
$\sqrt{n}$ iterations, if the maximum matching is not found yet, the length of the shortest augmenting path is $\geq 2\sqrt{n}+1$. Let $M$ be the current matching and $M^*$ be the maximum matching. $M^* \oplus M$ contains $|M^*| - |M|$ vertex-disjoint augmenting paths. Since each of these vertex disjoint augmenting paths is at least $2\sqrt{n}+1$ in length, it implies that the number of augmenting paths remaining in $M^* \oplus M$ is $\leq \sqrt{n}/2$ as the total number of vertices is $n$. After first $\sqrt{n}$ iterations, even if only one augmenting path is found in each successive iteration, we can still find a maximum matching in $O(\sqrt{n})$ iterations.
\end{proof}
\paragraph{}
Thus, the overall time complexity is $O(m\sqrt{n})$. In planar graphs, this comes to $O(n^{3/2})$. 
Hopcroft and Karp also showed that the total length of all augmenting paths found by the algorithm can be bounded by $O(n\log{n})$. We use this idea to bound the total length of all augmenting paths in the compressed residual graph on which we run a modified version of Hopcroft-Karp algorithm.
\section{Planar Separator Theorem}
Lipton and Tarjan showed in \cite{lipton} that a $n$-vertex planar graph can be divided into disjoint components of roughly equal size by removing a small set of vertices. Formally, Planar Separator theorem can be stated as follows: Given a planar graph $G$ with n vertices, there  exists a partition of vertices of G into $G_1$, $G_2$ and $S$ such that
\begin{itemize}
    \item $|G_1|, |G_2| \leq 2n/3$.
    \item $|S| \leq c\sqrt{n}$ where $c$ is a constant.
    \item $G_1$ and $G_2$ are edge disjoint.
\end{itemize}
\begin{figure}[!ht]
\centering
\includegraphics[width=0.6\textwidth]{./images/PlanarSeparator.png}
\caption{Planar Separation}
\label{fig:separator}
\end{figure}
\paragraph{Cycle Separator}
Extending Lipton-Tarjan's technique for finding separators, Miller \cite{miller} showed that it is possible to construct separators in planar graphs which are in the form of a cycle of small length ($O(\sqrt{n})$) such that the inside and the outside of the cycle each have at most $2n/3$ vertices.  Cycle separator is also referred to as \textit{Miller Separator}.
\section{Lipton-Tarjan Divide and Conquer Algorithm}
\label{Overview}
\paragraph{}
As one of many applications of planar separator theorem \cite{liptonapp}, Lipton and Tarjan showed that maximum cardinality matching problem in planar graphs can be solved efficiently in a divide and conquer fashion using planar separators. A planar separator can be used to subdivide the matching problem into two sub-problems, each of size at most $\frac{2n}{3}$. Maximum matching in each sub-problem is computed using a divide and conquer approach. When the sub-problem size becomes a small constant, we use Ford-Fulkerson algorithm to solve the sub-problem. Given the maximum matching for two sub-problems, the maximum matching for the current problem is computed in the merge step by introducing the boundary vertices. For ease of explanation, we will consider the merge step at the top most level of divide and conquer decomposition throughout this document in all chapters, unless stated otherwise. The same description for merge operation can be carried over to any sub-graph in the divide and conquer tree. The recurrence relation for this divide and conquer algorithm can be written as
\[T(n) = T(\alpha n) + T((1-\alpha)n) + g(n)  \]where $\frac{1}{3} \leq \alpha\ \leq \frac{2}{3}$ and $g(n)$ is the merge time.
\paragraph{}

Consider a bipartite graph $G(A \cup B, E)$ divided by planar separators into sub-graphs $X$ and $Y$ by removal of a set of boundary vertices, $S$. Before the merge step, we recursively find a maximum matching in $X$ and $Y$ which imply that the residual graphs $X_M$ and $Y_M$ have no augmenting paths. During the merge step, we compute a maximum matching $M^*$ in $G$. The symmetric difference of the current matching $M(X) \cup M(Y)$ with the maximum matching $M^*$ gives us a set of vertex-disjoint augmenting paths each passing through at least one vertex in $S$. This implies that $|M^*| - (|M(X)|+ |M(Y)|) \leq |S|$ or in other words, the number of remaining augmenting paths in $G$ is $O(\sqrt{n})$. 
\begin{lemma}
\label{sqrtn}
Number of augmenting paths remaining in $G$ at the start of the merge step of Lipton-Tarjan Divide and Conquer algorithm is $O(\sqrt{n})$.
\end{lemma}
\paragraph{}
Lipton and Tarjan showed that using Ford-Fulkerson algorithm to find one augmenting path at a time in merge step gives $g(n) = O(n^{3/2})$. The overall complexity of the recurrence relation above is dominated by merge time when g(n) is $\overset{\sim}{O}(n^c)$ where $c>1$. In such a case, the complexity of the algorithm is given by $g(n)$. Thus the overall complexity of Lipton-Tarjan algorithm for maximum cardinality matching is $O(n^{3/2})$.

\section{r-division of Planar Graphs}
\label{r-division}
\paragraph{}
Frederickson \cite{federickson} showed that the planar separator theorem of Lipton and Tarjan \cite{lipton} can be used to obtain an $\textit{r-division}$ of a planar graph $\G$ with $n$ vertices, which is the division of $\G$ into $O(n/r)$ edge disjoint sub-graphs called $regions$, each with $O(r)$ vertices and $O(r)$ edges.
\paragraph{}
Let $\{R_1(V_1,E_1),...,R_l(V_l,E_l)\}$ be the disjoint regions obtained by $r$-division of $G(A \cup B,E)$ where $l$ is $O(n/r)$. A vertex which is shared among two or more regions is a \textit{boundary vertex}. For a partition $R_j$, let $\K_j$ denote its set of boundary vertices. A vertex that belongs to just one region is called an \textit{internal vertex} of that region. The division ensures that every edge of $G$ is in exactly one region $R_j$. Specifically, the $r$-division $\{R_1(V_1,E_1),...,R_l(V_l,E_l)\}$ has the following properties: 
\begin{itemize}
   \item $\bigcup_j V_j = A \cup B$ and $E_j = \{(a,b) \mid (a,b) \in E, a,b \in V_j \}$. If vertices $a,b$ are common boundary vertices in multiple regions, include the edge $(a,b)$ in only one of the regions.
   \item $|V_j| = O(r)$ and $|\K_j| = O(\sqrt{r})$
    \item There are $O(n/r)$ partitions and $O(n/\sqrt{r})$ boundary vertices after $r$-division of $G$.
    \item All boundary vertices in a region $R_j$ lie in constant number of faces in planar embedding of $R_j$ (also called \textit{holes})
\end{itemize}
\paragraph{}
Like most algorithms which require cyclic ordering of boundary vertices in each region, we use Miller's cycle separator theorem \cite{miller} for the recursive decomposition ($r$-division). Fakcharoenphol and Rao \cite{frao} presented an $O(n\log{n})$ time recursive decomposition using Miller's separator where each region has a constant number of holes. $\textit{Holes}$ of a region $\R$ are the bounded faces of $\R$ introduced by the cycle separators and are not faces of original graph $\G$. Constant number of holes in each region is a necessity for our $\fivefour$ and $\sixfive$ algorithm as we will see in Chapter $\ref{chapter4}$. Our $\fourthree$ algorithm is however immune to number of holes in each region.

\section{Dense Distance Graphs}
\label{DDG Intro}
\paragraph{}
We use $\textit{dense distance graph}$ to answer connectivity queries between boundary vertices of a region (piece of $r$-division) for construction of edges of $H$. We maintain one DDG ($D_j$) for each region ($R_j$) of a $r$-division of $G$. The union $\bigcup_jD_j$ is called the DDG of entire graph $G$ (with respect to that $r$-division).
\paragraph{}
$D_j$ contains only the boundary vertices of $R_j$. $D_j$ includes a directed edge from one boundary vertex $u$ to another boundary vertex $v$ in $R_j$ if there is a directed path from $u$ to $v$ through edges within $R_j^M$ (residual graph of $R_j$). The edge also carries a weight representing the shortest path length from $u$ to $v$ within $R_j^M$. Since there are $O(r)$ pairs of boundary vertices in $D_j$, it could have $O(r)$ edges. We can ignore the edge weights if we are only interested in the connectivity.
\paragraph{}
Before we go into the details of construction of DDG, we introduce the Monge property in Section \ref{Monge property} which is satisfied by all shortest length paths between boundary vertices in planar graphs. We provide high-level details of decomposition of DDG into bipartite Monge groups and the  operations that can be performed on these groups using an associated data structures called Monge heaps. We also give an overview of implementing Dijkstra's algorithm using Monge heaps (FR-Dijkstra) that is in turn used to construct DDGs in divide and conquer fashion. For detailed analysis, refer \cite{frao}, \cite{mozes}. Some of the ideas in this section are borrowed for faster implementations of BFS and DFS which are described in Chapter \ref{chapter4}. 
\subsection{Monge property in Planar Graphs}
\label{Monge property}
\paragraph{}
Given ordered sets of boundary vertices $X$ and $Y$, we can define $\textit{Monge property}$ for shortest distances $d$ between pairs of elements in $X$ and $Y$ as follows: The sum of the shortest distances when the pairs do not cross is at most the sum when the pairs cross.
\begin{figure}[!ht]
\centering
\includegraphics[width=0.8\textwidth]{./images/monge.png}
\caption{Monge Crossing property for distances}
\label{fig:monge}
\end{figure}
Consider Figure \ref{fig:monge} where $u,v \in X$, and $x,y \in Y$, order wise $u \leq v$ and $x \leq y$, then \[d(u,x) + d(v,y) \leq d(u,y) + d(v,x)\]. As a direct consequence of this, we can see that the shortest paths do not cross in a Bipartite group i.e. if $d(v,x) \leq d(u,x)$, then $d(u,y)$  has to be greater than or equal to $d(v,y)$ to satisfy the Monge inequality. Otherwise, we arrive at a contradiction (see Figure \ref{fig:monge} $(b)$). Since the paths from $v \rightarrow x$ and $u \rightarrow x$ intersect at $w$ and $d(v,x)$ is shorter than $d(u,x)$ by our assumption, it also implies that $v \rightarrow w$ is shorter than $u \rightarrow w$. Thus, it is clear that $d(v,y) \leq d(u,y)$ if $d(v,x) \leq d(u,x)$. This is also called the \textit{non-crossing} property.
\subsection{Bipartite Monge Groups}
\label{mongeheaps}
\paragraph{}
To perform Dijkstra faster, the dense distance graph is decomposed into bipartite graphs. We know that in any dense distance graph, we can ensure that the boundary vertices lie in constant number of faces (holes) and have a cyclic ordering in the face they belong to. For the sake of simplicity, we will consider that the boundary vertices are in only one face and we can find a planar embedding such that the face becomes the infinite face. (Refer section 5 of \cite{frao} for handling constant number of holes). We split the boundary vertices into approximately two equal halves $X$ and $Y$ creating a \textit{complete} bipartite graph on $X$ and $Y$ with edges going from $X$ to $Y$. Using the same vertices, we define another bipartite graph with edges going from $Y$ to $X$. The edges in the bipartite graph obey the Monge property i.e. the shortest paths do not cross. Therefore, every vertex $x$ in $X$ has a contiguous interval of vertices in $Y$, say $I_x$ which have the shortest distance from $x$ amongst all the vertices in $X$. We continue dividing $X$ and $Y$ into almost equal halves successively (see Figure \ref{fig:mongedecomposition}) and end up with at most $O(k)$ bipartite groups for the piece, $k$ being the number of boundary vertices in the piece. For a region $R_j$ obtained from $r$-division, where $k$ is $O(\sqrt{r})$, we have $O(\sqrt{r})$ bipartite Monge graphs with each boundary vertex in at most $O(\log{r})$ groups and each edge in exactly one of the groups.
\begin{figure}[!ht]
\centering
\includegraphics[width=0.4\textwidth]{./images/Monge_decomposition.png}
\caption{Successive Bipartite Monge Decomposition}
\label{fig:mongedecomposition}
\end{figure}
\paragraph{}
We maintain a data structure for each Monge group which we call the Monge heap. We will use $(X,Y)$ to represent both bipartite Monge group and Monge heap depending on the context used and where differentiation is needed, we use $\mathcal{M}(X,Y)$ to represent Monge heaps. The nodes on the left of Monge group have labels associated with them and the label of a vertex $v$ on the right is given by $\delta(v) = min_{u \in X}\{\delta(u) + w(u,v)\}$ where $w(u,v)$ is the weight of the edge from $u$ to $v$ in the DDG which is also the shortest path from $u$ to $v$ in the region $R_j$ corresponding to the DDG that the Monge array is part of. When there is no edge from vertex $u$ to $v$ in DDG, it implies that there is no path from $u$ to $v$ in the the corresponding region of the original graph. In the Monge groups, we add an infinite weight edge from $u$ to $v$ when there is no path from $u$ to $v$. Therefore, the bipartite Monge groups are complete on the node set $X \cup Y$.
\paragraph{Online bipartite Monge Search}
Before diving into FR-Dijkstra, we describe this important subroutine of FR-Dijkstra on DDGs. In every Monge groups, we maintain a set of active nodes $A^* \subseteq X$, representing the frontier of Dijkstra search and set of \textit{matched nodes} $M \subseteq Y$ representing nodes whose Dijkstra shortest path parent has been discovered. Each Monge heap supports three operations. 
\begin{itemize}
   \item FINDMIN: Returns minimum unmatched node $y \in Y\backslash M$ from the heap. ($O(1)$ time)
   \item EXTRACTMIN: Adds the current minimum $y$ to $M$. For its parent $x \in A^*$, the interval $[i_-(x),i_+(x)]$ containing $y$ is split into $[i_-(x),y)$ and $(y,i_+(x)]$ and the shortest edges (found using Least Common Ancestor/Range Minimum Query data structure) in these intervals are added to the heap. Instead of maintaining multiple intervals per vertex $x \in X$, whenever we split intervals, we can also replace $x$ with two dummy nodes $x'$ and $x''$. One extra node is created in $X$ whenever a node in $Y$ is matched. This entire operation runs in $O(\log{(|X|+|Y|)}$ time.
    \item ACTIVATE($x_i$,$\delta(x_i)$): $x_i$ is activated in all the bipartite groups where it occurs on $X$ (left-hand side). Its interval in $Y$, $I_{x_i}$ is computed and other intervals are adjusted and the heap is updated. 
    \begin{figure}[!ht]
\centering
\includegraphics[width=0.6\textwidth]{./images/monge_array.png}
\caption{Intervals before and after vertex $x_8$ is activated}
\label{fig:mongearray}
\end{figure}
If the vertex $x_i$ is first to be activated in the group, its interval is whole of $Y$. Otherwise, walk up in $A^*$ until first $x_k$ whose $d(x_k,i_-(x_k)) < d(x_i,i_-(x_k))$. Do a binary search for $i_-(x_i)$ in the range $[i_-(x_k),i_+(x_k))$. Similarly, $i_+(x_i)$ can be found by walking down in $A^*$. After computing $I_{x_i}$, for nodes between $x_i$ and $x_k$, all their intervals become empty and their corresponding min in $Y\backslash M$ are removed from the heap. Do the same for nodes whose intervals are affected by walking down. New min for $x_k$ and for the corresponding node while walking down are updated in the heap. ACTIVATE has an amortized run time $O(\log{(|X|+|Y|)}$ per operation. Figure \ref{fig:mongearray} illustrates interval adjustment when vertex $x_8$ is activated. Note that $y_3$ and $y_9$ are not in any intervals implying that they have already been matched.
\end{itemize}

\subsection{Efficient Dijkstra Search in Dense Distance Graphs}
\label{FR}
\paragraph{}
FR- Dijkstra is an efficient Dijkstra implementation on Dense distance graphs due to Fackcharoenphol and Rao. FR-Dijkstra algorithm constructs a single source shortest path tree on the vertices of the DDG (boundary vertices of the original graph) with some boundary vertex as source in time proportional to number of vertices in DDG while the traditional Dijkstra algorithm runs in time proportional to the number of edges in the DDG.
\paragraph{}
By combining DDGs of all regions of $r$-division, we can perform FR-Dijkstra on the boundary vertices of the entire graph. The run time  is proportional to $O(n/\sqrt{r})$ (the total number of boundary vertices) instead of $O(n)$ which is the number of edges between boundary vertices across all DDGs. 
\paragraph{}
 Each DDG is decomposed into bipartite monge groups. In addition to a heap for each bipartite group, FR-Dijkstra algorithm uses a global heap $\Queue$ having vertices with smallest labels from each bipartite Monge group instance $(X_i,Y_i)$. In each iteration, a vertex $v$ having smallest label in $\Queue$ is extracted and the Monge heap $(X,Y)$ that contributed $v$ updates its new smallest vertex to the global heap $Q$ after adding $v$ to $M$. Since a vertex can be in $O(\log{r})$ bipartite groups in every region of $r$-division that it is part of, it may be extracted from $\Queue$ multiple times with different labels from different local Monge heaps belonging to different regions. However, its Dijkstra distance is fixed the first time it is extracted. After a vertex $v$ is extracted for the first time, it is added to the Dijkstra search frontier using ACTIVATE which adds $v$ to $A^*$ and updates all the Monge heaps containing vertex $v$ in X and their representatives in $\Queue$.
\paragraph{}
Run time of FR-Dijkstra is bounded by the number of calls to FINDMIN, EXTRACTMIN and ACTIVATE. EXTRACTMIN and ACTIVATE are called at most once per vertex in each Monge heap and FINDMIN is called whenever EXTRACTMIN or ACTIVATE is called. In region $R_{j}$, its DDG ($D_j$) has each boundary vertex appearing in $O(\log{r})$ Monge heaps and this bounds the total number of operations to $O(\sqrt{r}\log{r})$ per region. Each operation takes at most $O(\log{r})$. Therefore FR-Dijkstra takes $O(\sqrt{r}\log^{2}{r})$ time per region $R_{j}$ or $O((n/\sqrt{r})\log^{2}{n})$ time in the entire graph.
\paragraph{}
We use FR-Dijkstra with slight changes to do BFS on compressed residual graph $H$ in Chapter \ref{chapter4}. Theoretically, BFS is just Dijkstra's algorithm with unit edge costs. We reserve the pseudo code for Chapter \ref{chapter4}. We also modify FR-Dijkstra to do FastDFS on $H$ in Chapter \ref{chapter4}. 
\subsection{Construction of DDG}
\paragraph{}
Dense distance graph $D_j$ of a region $R_j$ is constructed in a divide and conquer approach. The sub-graph $R_j$ is recursively divided into smaller pieces using cyclic planar separators forming a decomposition tree. A boundary vertex in level $i$ of decomposition is also a boundary vertex in level $i+1$ sub-piece. In addition to that, decomposition of level $i$ piece to form level $i+1$ sub-pieces can introduce new boundary vertices in each of the level $i+1$ sub-pieces. The dense distance graph for the parent at level $i$ of decomposition is constructed from the dense distance graphs of its children at level $i+1$. This is possible through FR-Dijkstra routine which runs in time proportional to number of boundary vertices in both the children which is  $O(\sqrt{v})$ more the number of boundary vertices in the parent, $v$ being the number of vertices in the parent. Fakcharoenphol and Rao [cf section 5, \cite{frao}] also proposed a 3-level decomposition which ensures an exponential decrease in number of total vertices and boundary vertices for every 3 levels of decomposition and restricts the count of holes in every piece of decomposition tree to not exceed a constant value. 
\paragraph{}
Computing the shortest path tree from each boundary vertex using FR-Dijkstra takes $O(\sqrt{r}\log^2{r})$ time. We invoke FR-Dijkstra for all boundary vertices. Therefore the total time taken for all Dijkstra computations is $O(\sqrt{r}\sqrt{r}\log^2{r}) = O(r\log^2{r})$. Since there are $O(\log{r})$ levels in the recursive decomposition, the overall time to compute dense distance graph per region takes time $O(r\log^{3}{r})$. The query time to check for connectivity from vertex $u$ $\rightarrow$ $v$ takes $O(\log{r})$ time. Data structures with better construction time and query time exist for creation of dense distance graph to answer connectivity queries. Klein's multiple source shortest path data structure \cite{klein2005} has a construction time of $O(r\log{r})$ per region and query time of $O(\log{r})$. Thorup's data structure \cite{thorup} has a $O(r\log{r})$ construction time and can answer connectivity queries in constant time.


