\chapter{ New Matching Algorithm}
\label{chapter3}
\markright{Mudabir Kabir Asathulla \hfill Chapter 3. New Matching Algorithm \hfill}
\paragraph{}
Our algorithm adapts Lipton-Tarjan's divide and conquer technique as described in Section \ref{Overview}. We improve the merge time $g(n)$ from $O(n^{3/2})$ to $\sixfivefast$ by exploiting planar graph properties. We first present the details of a simpler version of our merge algorithm which has a run time of $\fourthree$. We also provide proof of correctness and run-time analysis. We conclude this chapter by stating the similarity between our merge algorithm and Hopcroft-Karp algorithm.
\paragraph{Algorithm Organization}
We begin by describing two operations that are performed at the beginning of our merge algorithm namely
\begin{itemize}
   \item  Preprocessing (Section \ref{Preprocessing})
   \item Construction of Compressed Residual Graph $H$ (Section \ref{Construction of H})
\end{itemize}
\paragraph{}
We then perform a Hopcroft-Karp style algorithm on $H$ to compute maximum matching in $G$. The details of the Hopcroft-Karp style algorithm is provided in Section \ref{Merge Algorithm}.
\section{Convention for Notation}
We are given a bipartite graph $G$. We refer to its residual graph as $G_M$. The vertex and edge sets of $G$ and $G_M$ are identical (except for the directions) and a matching, alternating path or an alternating cycle in $G$ is also a matching, alternating path or an alternating cycle in $G_M$. If $P$ is a subset of edges in $G$, we will also use $P$ to denote the same subset of edges in $G_M$, the directions of the edges being determined by whether or not an edge is in $M$. We know that $r$-division partitions the edges of $G$ into regions $\bigcup_j R_j$. Since $G$ and $G_M$ have the same underlying set of edges, we use $R_j$ to also represent regions of $G_M$. Dense distance graph $D_j$ corresponding to each region $R_j$ is constructed from boundary vertices of $R_j$. We use $\K_j$ to represent boundary vertices of both $R_j$ and $D_j$.
\paragraph{}
$H$ is a compressed residual graph that we construct using the $r$-division boundary vertices of $G_M$ (details in Section \ref{Construction of H}) and the unmatched internal vertices in each region of $G_M$. We use the boundary vertices of $G_M$ to define regions $\bigcup_j \RH{j}$ in $H$ and just like in $D_j$, we also use $\K_j$ to represent boundary vertices of region $\RH{j}$ in $H$. The compressed residual graph changes whenever $G_M$ changes. For convenience, we will still use a single notation $H$ to represent the changing compressed residual graph. We also state explicitly whether we are referring to the compressed residual graph before or after the change to avoid confusion for readers.
\section{Preprocessing}
\label{Preprocessing}
\paragraph{}
There are at most $O(\sqrt{n})$ augmenting paths remaining at the beginning of merge step (Lemma \ref{sqrtn}). We find r-division of $G(A \cup B,E)$. In each region ($R_j$) of $G$ after $r$-division, we do DFS iteratively from unmatched vertices of type $B$ to find augmenting paths lying wholly within $R_j$. An unmatched vertex can be an internal vertex or a boundary vertex. 
\paragraph{}
Each DFS takes $O(r)$ time. We need to do at most $O(\sqrt{n})$ iterations of DFS in total from unmatched internal vertices as there cannot be more than $O(\sqrt{n})$ unmatched internal vertices at the beginning of merge step. Thus the total time taken to do DFS from unmatched internal vertices is $O(\sqrt{n}r)$. Since the total number of boundary vertices in each region $R_j$ of graph $G$ after $r$-division is $O(\sqrt{r})$ and there is $O(n/r)$ regions, we can bound the total number of iterations of DFS from unmatched boundary vertices to be $O(n/\sqrt{r})$. Even though a boundary vertex can belong to multiple regions, it can have a matching in at most one region. Once a boundary vertex is matched in a region, we need not repeat DFS from this vertex in the remaining regions that contain it. The total time taken to do DFS from unmatched boundary vertices across all regions is $O(n\sqrt{r})$. For any $r < n$, $n\sqrt{r} > \sqrt{n}r$. Thus the preprocessing step has $O(n\sqrt{r})$ run time. 
\paragraph{}
Preprocessing step ensures that augmenting paths within each region are eliminated and the remaining augmenting paths must span multiple regions. In other words, the remaining augmenting paths in $G_M$ should include at least one matched boundary vertex.
\begin{lemma}
\label{After preprocessing}
After the preprocessing step, there are $O(\sqrt{n})$ augmenting paths remaining in $G_M$ and there is no augmenting path which lies wholly inside a region $R_j$.
\end{lemma}
\section{Compressed Residual Graph H}
\label{Construction of H}
\paragraph{}
Given a current matching M after the preprocessing step, the sparse graph $H$ is a \textit{multi-graph} constructed on the boundary vertices and free vertices of $A \cup B$. Let $\AF$ and $\BF$ denote the set of free vertices of $A$ and $B$ respectively after finding maximum matching in each region. The vertex set of $H$, denoted by $\vh$, will contain all the boundary vertices i.e., $\cup^l_{j=1}\K_j$. Therefore, every  free vertex that is also a boundary vertex will automatically be in $\vh$. For every partition $R_j(V_j,E_j)$, if at least one free vertex from $\AF \cap V_j$ is not a boundary vertex, i.e., $(V_j \backslash \K_j) \cap \AF $ $\neq \emptyset$, a special vertex $a_j$ is added in $\vh$ to represent all the free vertices of $(V_j \backslash \K_j) \cap \AF$. Similarly, vertex $b_j$ is added in $\vh$ for the set of free vertices of $(V_j \backslash \K_j) \cap \BF$. We call these additional vertices of $\vh$, $a_j$ and $b_j$, \textit{free internal vertices}. The vertex set $\vh$ of $H$ is thus given by $\vh$ = $\bigcup ^l_{j=1}(\K_j \cup \{a_j,b_j\})$. The nodes of $H$ are classified depending on whether they are from $A$ or $B$ as follows: $A_H =  \bigcup_j((\K_j \cap A)\cup \{a_j\})$ and $B_H =  \bigcup_j((\K_j \cap B) \cup \{b_j\}) $. Clearly, $\vh = A_H \cup B_H$. We refer to $\HSet{A}{F}$ = $(A_H \cap \AF) \cup$ $\bigcup_ja_j$ and $\HSet{B}{F}$ = $(B_H \cap \BF) \cup$ $\bigcup_jb_j$ as the free vertices of $A_H$ and $B_H$.

\paragraph{}
After defining the vertex set $\vh$ of $H$, edges between these vertices are constructed as follows. In order to define the edge set of $H$, we consider the residual graph $G_M$ after preprocessing where we find maximum matching in each region of the $r$-division. Let $M_j$ be the edges of the matching $M$ that are contained in $R_j$, i.e., $M_j = M \cap E_j$. The edges in $H$ are of three types.
\begin{itemize}
   \item  $u,v \in \K_j$ are both boundary vertices and there is a directed path from $u$ to $v$ in $G_M$ that only passes through the edges of $R_j$. Note that $H$ is a multi-graph in general because of edges of this type; multiple regions can contribute to edges between same pairs of boundary vertices.
   \item  $u = b_j$ and $v \in \K_j$, and there is a directed path in $G_M$  from some free vertex in $B_F \cap(V_j\backslash \K_j)$ to $v$ that only passes through the edges of $R_j$. 
   \item  $u \in \K_j$ and $v = a_j$, and there is a directed path  in $G_M$ from $u$ to a vertex $v$ in the set $A_F \cap(V_j\backslash \K_j)$ that only passes through the edges of $R_j$. 
\end{itemize}
We will denote by $E_j^H$, the set of edges in $H$ between vertices $u,v \in (\K_j \cup \{a_j, b_j\}$). For every edge $(u,v) \in \Ej$, the \textit{projection} of the edge $(u,v)$ on the residual graph $G_M$ is the corresponding shortest directed path from $u$ and $v$ in $G_M$ using only edges of $R_j$. This can be obtained by doing a BFS from $u$ in $R_j$. 
\begin{lemma}
H has $O(n/\sqrt[]{r})$ vertices and O(n) edges.
\end{lemma}
\begin{proof}
The vertex set of $H$ consists of free internal vertices and set of boundary vertices. At most two free internal vertices are added per region. Since there are $O(n/r)$ partitions, total number of free internal vertices is $O(n/r)$. On the other hand, there are $O(\sqrt[]{r})$ boundary vertices in each region in $H$. Therefore the total number of boundary vertices in $H$ can be bounded by $O(n/r) * O(\sqrt[]{r}) = O(n/\sqrt[]{r})$. This also bounds the total number of vertices in $H$. 
\paragraph{}
In each region, every pair of boundary vertices may have an induced edge between them. Therefore there are $O(r)$ such edges per region. There are at most $O(\sqrt[]{r})$ edges per region where one end vertex is a free internal vertex. So, the bound on total number of edges in a region is $O(r)$. Since there are $O(n/r)$ partitions, the total number of edges in all the regions of $H$ is $O(n)$. 
\end{proof}
\paragraph{}
For computing $H$, we construct a \textit{dense distance graph} for each region as described by Fakcharoenphol and Rao \cite{frao}. We covered dense distance graphs in section \ref{DDG Intro}. The dense distance graph stores all-pairs shortest path distances between boundary vertices in the region. %Fakcharoenphol and Rao showed that Dijkstra's algorithm on dense distance graphs can be performed in the order of number of vertices instead of the number of edges. This has given way to many state-of-the-art algorithms for shortest paths or max-flow algorithms in planar graphs. We will also use dense distance graphs to design faster BFS and DFS.
\paragraph{}
Let $\RH{j}$ be a sub-graph in $H$ with vertex set $(\K_j \cup \{a_j, b_j\})$ and edge set  $\Ej$. We refer to $\RH{1},\RH{2} \ldots \RH{l}$ as regions of $H$. Connectivity between each pair of boundary vertices in the region can be established in $O(\log{r})$ time after construction of dense distance graph and there are $O(r)$ combinations of pairs of boundary vertices. To compute edges of the type $(u,v) \in b_j \times \K_j$, we add an additional vertex $\tilde{b}$ to the subset of the residual graph $G_M$ defined by matching $M_j$ in $R_j$ and add an edge from $\tilde{b}$ to every vertex in $(B_F \cap V_j)\backslash\K_j$. Next, we execute BFS from $\tilde{b}$ in the subset of residual graph $G_M$ in the region $R_j$ and include the edge $(u,v)$ in $R_j^H$ only if there is path to $v$ from $\tilde{b}$ in the BFS search. BFS takes $O(r)$ time as the number of edges is $O(r)$ in $R_j^M$. Using a similar approach with the edges of $G_M$ reversed and a newly added vertex $\tilde{a}$ in $R_j$, we compute edges of the type $(u,v) \in \K_j \times a_j$. This yields the following Lemma:
\begin{lemma}
The edges of H in any partition $\RH{j}$ can be computed in $O(r\log{r})$ time.
\end{lemma}
\begin{proof}
While constructing $H$, we also store information on immediate neighbors of each vertex. In each region $\RH{j}$, for every vertex $u$ in the region, we maintain an adjacency list of all vertices that it has edges to, which we refer to as $\textit{neighbors}$ of $u$ in $\RH{j}$. With a constant number of holes (say $h$) in each region, instead of maintaining a single neighbors list for each vertex, we need to maintain $h$ lists of neighbors for each vertex, one each for neighbor vertices lying on a particular face. Each boundary vertex $u$ also has separate list for edges of type $(u,a_j)$. Since a boundary vertex belongs to multiple regions, it will have one or more $\textit{neighbors}$ lists for each region it belongs to depending on the number of holes in that region. Moreover, boundary vertices have a cyclic order in their respective face (hole). Therefore, for each vertex, the neighbors list corresponding to each hole has vertices stored in cyclic order. For the sake of simplicity, for the rest of chapter \ref{chapter3} and for chapter \ref{chapter4}, we will assume that all boundary vertices lie on the infinite face and for each vertex $u$ in a region, there is only one neighbors list in that region denoted by $\N{u}{j}$ comprising of just boundary vertices which are neighbors of $u$. $u$ also maintains a separate list for edges of type $(u,a_j)$ as mentioned before. All descriptions henceforth will make this assumption and can be easily carried over to the handle constant number of holes as well.
\end{proof}
\begin{definition}
We define \textit{Augmenting path in $H$} as a simple directed path (no cycles) in $H$ from a free vertex in $\HSet{B}{F}$ to a free vertex in $\HSet{A}{F}$.
\section{Projection and Lifting}
\end{definition}
\paragraph{}
Up until now, we have described the creation of the compressed graph $H$. Before diving into our algorithm, we introduce two operations involving $G$ and $H$, namely $\textit{projection}$ and $\textit{lifting}$.
\subsection{Projecting a path.} 
To project a path $\PH$ in the compressed residual graph $H$ to a path $P$ in residual graph $G_M$, each edge $(u,v)$ of $\PH$ is to be replaced by some directed path between the end vertices $u$ and $v$ in $G_M$. Edges $(u,v)$ of type $u,v \in \K_j$ can be projected to $G$ by querying the dense distance graph $D_j$ which returns the shortest path between $u$ and $v$. An edge $(u,v)$ of type $u = b_j, v \in \K_j$  (or $u \in \K_j, v = a_j$) can be projected to $G$ in just the same way they were constructed by doing BFS from $\tilde{b}$ (or $\tilde{a}$) and identifying a free vertex in $(V_j\backslash\K_j)\cap B_F$ (or $(V_j\backslash\K_j)\cap A_F$) that has a path to (or from) the boundary vertex.
\begin{figure}[!ht]
\centering
\includegraphics[width=1.0\textwidth]{./images/projection.png}
\caption{A path in $G_M$ is lifted to $H$. An edge in $H$ is projected to shortest path in $G_M$.}
\label{fig:projection}
\end{figure}

\subsection{Lifting a path.} 
Consider a directed path $P$ in $G_M$. Among the vertices of $P$, let $p_{i_1},p_{i_2},\ldots,p_{i_l}$ with $i_1 < i_2 < i_3 < \ldots < i_l$, be all its boundary vertices. Let $P_{i_t}$ be the sub-path of $P$ lying between the vertices $p_{i_t}$ and $p_{i_{t+1}}$. Note that $P_{i_0}$ will be the sub-path in $P$ appearing before the vertex $p_{i_1}$ and $P_{i_l}$ is the sub-path in $P$ appearing after the vertex $v_{i_l}$. Also, note that if $p_{i_t}$ and $p_{i_{t+1}}$ are adjacent to each other in $P$, then $P_{i_t}$ will contain only one edge, i.e.,  the edge with $p_{i_{t}}$ and $p_{i_{t+1}}$ as endpoints. We will map any sub-path $P_{i_t}$ with $u$ and $u^{\prime}$ as its first and last vertex to an edge $(v,v')$ in $H$. This edge $(v,v')$ is referred to as the $\textit{lift}$ of the path $P_{i_t}$ and is constructed as follows. Note that if both $u$ and $u^{\prime}$ are boundary vertices, we set $v \leftarrow u$ and $v' \leftarrow u^{\prime}$. Suppose, $u$ is a free internal vertex of $B$ in partition $R_j$. In this case, we set $u$ to $b_j$. A similar construction is applied in the case where $u^{\prime}$ is a free internal vertex of $A$. Let $e^{\prime}_{i_t}$ be the lift of the path $P_{i_t}$. It is easy to see that the path $<e^{\prime}_{i_0},e^{\prime}_{i_1},e^{\prime}_{i_2},\ldots,e^{\prime}_{i_l}>$ is a path in $H$. We say that this path $\PH$ in $H$ is obtained by lifting the path $P$ to $H$. As a consequence of the lifting operation, we get the following corollary.
\begin{corollary}
\label{maxmatch}
If the matching M is not a maximum matching in G, then there is an augmenting path in H.
\end{corollary}
\begin{proof}
Let $M^*$ be optimal matching in $G$. $M^*\oplus M$ gives a set of vertex disjoint augmenting paths in $G_M$. Any augmenting path  in $G_M$ starting at $u \in B_F$ and ending at $u^{\prime} \in A_F$ is lifted to a path in $H$ beginning at $v \in \HSet{B}{F}$ and ending  at $V_H \in \HSet{A}{F}$ by above construction of lifting which also happens to be an augmenting path in $H$ by definition.
\end{proof}
\begin{lemma}
\label{disjoint}
Let $P_1$ and $P_2$ be two vertex-disjoint directed paths in $G_M$ and $Q_1$ and $Q_2$ be the paths obtained by lifting them to the graph $H$. Let $Q^{\prime}_1$ (resp $Q^{\prime}_2$) be all the vertices on the path $Q_1 (resp$ $Q_2)$ except for its start and end vertex, then
\begin{center}
$Q^{\prime}_1 \cap Q^{\prime}_2 = \emptyset$
\end{center}
\end{lemma}
\begin{proof}
This is again a consequence of lifting operation. Since paths $P_1$ and $P_2$ are vertex disjoint in $G_M$, it also implies that they share no common boundary vertices between them. When these paths are lifted to $H$, $Q_1$ and $Q_2$ will also have a disjoint set of boundary vertices. A path in $H$ comprises of just the boundary vertices except for possibly the start and the end vertex which could of type $b_j$ and $a_j$ respectively. By discarding the first and last vertex from $Q_1$ and $Q_2$, the intermediate vertices are only boundary vertices. Thus we get $Q^{\prime}_1 \cap Q^{\prime}_2 = \emptyset$. 
\begin{figure}[!ht]
\centering
\includegraphics[width=1.0\textwidth]{./images/Disjoint_paths.png}
\caption{Vertex disjoint paths in $G$ (shown in red) have disjoint boundary vertices in $H$}
\label{fig:Disjointpaths}
\end{figure}
\end{proof}

\section{Merge Algorithm}
\label{Merge Algorithm}
\paragraph{}
After performing the preprocessing (Section \ref{Preprocessing}) and construction of $H$ (Section \ref{Construction of H}), we execute a Hopcroft-Karp style algorithm on $H$ to compute maximum matching in $G$. We will show in Section \ref{Algo Efficiency} that this improves the merge time of our  divide and conquer algorithm.
\paragraph{}
Our algorithm runs in phases till we have a maximum/perfect matching in $G$. In each phase, we do the following steps.
   
\paragraph{BFS}
\label{BFS}
We construct a layered graph in $H$ by doing a BFS from the free vertices in $\HSet{B}{F}$ similar to the layered graph construction in Hopcroft-Karp algorithm described in Section \ref{HK revisited}.  Let $\mathcal{V}$ be the set of vertices in the layered graph which includes $\HSet{B}{F}$ and all the vertices of $H$ that are reachable from any vertex in $\HSet{B}{F}$ with distance less than or equal to the shortest augmenting path length $\mathcal{L}$ in $H$ at the beginning of the iteration. The result of the BFS procedure is a labeling of all vertices in $\mathcal{V}$ with a layer number $\layer{.}$. For all $u \in \HSet{B}{F}$, $\layer{u} = 0$. For all $v \in \mathcal{V}\backslash \HSet{B}{F}$, $\layer{v}$ is the length of the shortest directed path in $H$ from some vertex in $\HSet{B}{F}$ to $v$.
\paragraph{FINDAUGPATH}
\label{FINDAUGPATH}
After constructing the BFS layered graph, FINDAUGPATH procedure performs partial DFS from $\HSet{B}{F}$ in the layered graph to find a maximal set of shortest length augmenting paths in $H$. An arbitrary vertex $v$ is chosen in $\HSet{B}{F}$ and a DFS is done from $v$ in $H$. At any stage during the search, a partial directed path $\PHH$ is maintained which begins at $v$ and ends at some vertex $u$. FINDAUGPATH also keeps track of the vertices that have been visited so far during the DFS. An outgoing edge from $u$ is chosen such that the next vertex $u'$ is an unvisited vertex and has $L(u') = L(u)+1$. $u'$ is then added to the path $\PHH$. $u'$ is marked visited and the search continues from $u'$. If there is no such $u'$, $u$ is removed from $\PHH$ and search is repeated from the predecessor of u in $\PHH$ choosing another edge leading to an unvisited vertex with the same layer number as $u$. If $u'$ $\in$ $\HSet{A}{F}$, an augmenting path $\PH$ is found in $H$ and AUGMENT procedure is invoked to augment along the projection $P$ of this path in $G_M$.  After AUGMENT procedure returns or if no augmenting path is found during DFS from $v$ , FINDAUGPATH initiates a new search from the next unvisited vertex in $\HSet{B}{F}$.
\paragraph{AUGMENT}
The AUGMENT procedure takes as input, an augmenting path $\PH$ in $H$. We denote a partition $R_j$ of $G$ as  \textit{affected} if the path $\PH$ has at least one edge from the edges of $H$ in $\Ej$. Let $\hat{R}$ be the set of all affected partitions. Each directed edge $(u,v)$ in $\PH$ belonging to $\Ej$ is projected in the corresponding region $R_j$. Let $P$ be the projection of $\PH$ on $G_M$. By rules of projection, $P$ also starts and ends in a unmatched vertex. We will show in Lemma \ref{simplepath} that $P$ is a simple path and contains no self-intersections. Therefore, $P$ is an augmenting path in $G_M$. After augmenting along $P$, the residual graph $G_M$ changes and the edges in each partition in $\hat{R}$ are recomputed in $H$. Reconstruction can be done in each region using the same data structures that we used to construct $H$ in Section \ref{Construction of H}.
\paragraph{}
In each phase of our Hopcroft-Karp style algorithm, FINDAUGPATH finds a maximal set of shortest length augmenting paths in $H$ (Lemma \ref{I1}) which are also boundary vertex disjoint (Lemma \ref{norepeat}). Unlike the Hopcroft-Karp algorithm, we augment in $G_M$ immediately after finding an augmenting path during partial DFS in $H$. Since $H$ changes (only \textit{affected} regions) after each augmentation, the new compressed residual graph $H$ may introduce new augmenting paths. We show in Lemma \ref{auglength} that all such augmenting paths are of length $\geq \mathcal{L}$ which is the length of the shortest augmenting path in the beginning of the phase. Also, since $H$ changes after each augmentation, it may affect the layer numbers of some vertices in $H$. For this reason, it may seem necessary to perform BFS again to construct new layered graph after each augmentation. We, however show that it suffices to do BFS just once at the beginning of each phase (Lemma \ref{layering}, \ref{auglength}, \ref{norepeat}) and that vertices whose layer numbers change will not be part of shortest length augmenting path in the current phase. We also show that the length of the shortest augmenting paths in $H$ increases (Lemma \ref{I1}) after each phase of our algorithm and the number of iterations required to compute maximum matching is $O(\sqrt{V_H})$ (Lemma \ref{lem:iterations}).
\paragraph{}
Our algorithm maintains the following invariant.
\begin{itemize}
   \item[(I1)] Projection $P$ of an augmenting path $P'$ in $H$ onto $G_M$ is a simple path i.e., the path $P$ does not have any self-intersections.
\end{itemize}
\section{Proof of Correctness}
\paragraph{}
In this section, we state and prove some properties to justify the correctness of our Hopcroft-Karp style algorithm.
\paragraph{}
We assume the invariant (I1) for proving lemmas \ref{layering} to \ref{I1}. We later prove the invariant (I1) in Lemma \ref{simplepath}.
\begin{definition}
An edge $(u,v)$ in $H$ is called level respecting if $L(v) \leq L(u)+1$ and the edge is said to be in the \textit{level} $L(u)$ .
\end{definition}
$L(.)$ refers to layer numbers assigned to vertices by the BFS procedure of our Hopcroft-Karp style algorithm. Before finding the augmenting paths in $H$, all the edges in $H$ between vertices in layered graph are level respecting.
\begin{lemma}
\label{lemmanew1}
Two level respecting edges $(u,v)$ and $(u',v')$ in $H$ lying in the same region $\RH{j}$ and satisfying the following conditions
\begin{enumerate}
\item $L(v)= L(u) +1$, $L(v')=L(u')+1$
\item $L(u') \geq L(u) +1$
\end{enumerate}
will always have vertex-disjoint projections.
\end{lemma}
\begin{proof}
Consider two level respecting edges $(u,v)$ and $(u',v')$ in region $\RH{j}$ satisfying the above 2 conditions. From the two conditions, we can infer $L(v') \geq L(u)+2$. Let us assume that the projections of $(u,v)$ and $(u',v')$ share a common vertex $w$. This would mean that $u$ has a path to $v'$ through $w$ in $G_M$ and by rules of construction of $H$, there should be an edge $(u,v')$ in $H$ assigning $L(v')=L(u)+1$. Thus, we arrive at a contradiction.
\end{proof}
\paragraph{}
Reversing some edges in the region $R_j$ of $G_M$ can create and destroy edges in the region $\RH{j}$ of $H$ while all other regions of $H$ remain unaffected. In Lemmas \ref{lemmanew2} to \ref{layering}, we state and prove some properties that are obeyed by new edges introduced in $H$ due to changes in the residual graph $G_M$.
\begin{definition}
A directed path from vertex $u$ to $v$ in $G_M$ (or $H$) is of shortest length if the path uses minimum number of edges among all the paths from $u$ to $v$ in $G_M$ (or $H$).
\end{definition}
\begin{lemma}
\label{lemmanew2}
If the projection of an edge $(u,v)$ with $L(v)= L(u)+1$ is reversed in $G_M$, the new  edges created in $H$ will be level respecting and will have a level greater than or equal to $L(u)$.
\end{lemma}
\begin{proof}
After reversing the projection $P$ of edge $(u,v)$, new paths are introduced between boundary vertices of $R_j$ in $G_M$ that use one or more reversed edges of $P$. This could lead to new edges being introduced in $H$  and each of these edges have least one of the reversed edges of $P$ in their projection.
\paragraph{}
Let $(u',v')$ be one of the newly formed edges in $H$. Projection of $(u',v')$ uses at least one of the reversed edges of $P$. Let $w$ be the first common vertex which is both in projection of $(u',v')$ and in $P$. 
 Before reversing the projection $P$, there was a directed path from $w$ to $v$ in $R_j$  along $P$. This implies that $u'$ also had a path through $w$ to $v$ before reversing $P$. Thus, by construction of $H$, there must have been an edge $(u',v)$ in $H$ before reversing $P$ as shown in the second diagram of Figure \ref{fig:Layering}. Let $L(u)=i$  and $L(v)= i+1$. Since the edge $(u',v)$ is level respecting and $L(v)=i+1$, we can infer that $L(u') \geq i$.

\paragraph{}
After reversing $P$, $u'$ which had a path to $v$ through $w$ would now have a path to $u$ through $w$ using the reversed edges of $P$. $u'$ will also have a path to all neighbors of $u$ after reversal of $P$. Thus $v'$ in the newly  edge could either be $u$ or a neighbor of $u$ in $\RH{j}$ after reversal of $P$. If $v'$ is a neighbor of $u$, $(u,v')$ must have existed even before reversing $P$. $(u,v')$ is also level respecting and therefore $L(v') \leq i + 1$. If $v'$ is $u$, it would still satisfy the condition $L(v') \leq i + 1$ as $L(u) = i$. Since $L(u') \geq i$ and $L(v') \leq i + 1$, we can conclude that the newly added edge $(u',v')$ also satisfies the definition of level respecting.
\begin{figure}[!ht]
\centering
\includegraphics[width=1.0\textwidth]{./images/layers.pdf}
\caption{$L(u)$ and $L(v')$ can only increase or remain same after augmentation.}
\label{fig:Layering}
\end{figure}
Moreover, the newly  added edge will have level greater than or equal to $i$ since $L(w) \geq i$.
\end{proof}
\begin{lemma}
\label{newlemma3}
Reversing the projection of an edge $(u,v) \in \RH{j}$ where $L(v)= L(u)+1$ does not create or destroy a level respecting edge with level $< L(u)$ in $\RH{j}$.
\end{lemma}
\begin{proof}
We showed in Lemma $\ref{lemmanew2}$ that reversing the projection of $(u,v)$ only introduces level respecting edges in $H$. We also showed that these edges are at level $\geq L(u)$ in $\RH{j}$. We now show that no level respecting edge with level $< L(u)$ is destroyed by reversing the projection of $(u,v)$.
\paragraph{}
%Reversing the projection of $(u,v)$ would affect all the paths which used one or more edges in the projection. Let $L(u)=i$. 
Projection of any level respecting edge $(u',v')$ at level $< i$ will only have vertices with $L(.) \leq i$ and it should also be vertex-disjoint (hence also edge-disjoint) from the projection of $(u,v)$. Otherwise, $u'$ would have a path to $v$ in $R_j$ through the common vertex of two projections and the corresponding edge $(u',v)$ in $H$ would violate level respecting property. This contradicts the fact that all edges in $H$ are level respecting. Thus reversing the projection of $(u,v)$ does not remove any level respecting edge at level $< i$. 
\end{proof}
\paragraph{}
Using Lemmas \ref{layering} to  \ref{norepeat}, we will show that the boundary vertices which are visited by the FINGAUGPATH can be discarded as they will never be part of a newly found augmenting path in the same phase of the algorithm.
\paragraph{}
After finding an augmenting path $\PH$ in $H$, its projection on $G_M$, $P$ is augmented, causing each of its edges to get reversed in $G_M$. When the path corresponding to projection of an edge in $\PH$ gets reversed, it can lead to new edges being created between the vertices in $H$ in the region affected, which can affect the layer numbers of many vertices that were computed by the $\textit{BFS}$ procedure.  % This helps us to justify the fact that we only do BFS once at the beginning of each phase.
\begin{lemma}
\label{newlemma0}
The new edges introduced in $H$ after augmenting the projection of $P'$ in $G$ satisfy the level respecting property.
\end{lemma}
\begin{proof}
 We know that reversing the projection of an edge in $\RH{j}$ does not affect edges of $H$ in other regions. We also saw in Lemma \ref{newlemma3} that reversing the projection of an edge $(u,v)$ in $\RH{j}$ where $L(v) =L(u)+1$ does not affect the level respecting edges at lower levels. Since reversing the projection of an edge in $P'$ does not affect the edges of $H$ in other regions and in the lower levels of the same region, we can consider the effect of augmenting the path $P$ (projection of $P'$) as being same as incrementally reversing the projection of edges in $P'$, one at a time from the end of the path $\HSet{A}{F}$ to the beginning $\HSet{B}{F}$. 
\paragraph{}
After augmenting the projection of each edge in $P'$, the newly created edges in $H$ are also level respecting as shown in Lemma \ref{lemmanew2}. Extending this property to all the edges in $P'$, we can say that all the newly introduced edges in $H$ after augmenting the path $P$ would be level respecting.
\end{proof}
\begin{lemma}
\label{layering}
Layer number of vertices in $H$ assigned by BFS step do not decrease after augmenting a path $P$ in G.
\end{lemma}
\begin{proof}
As shown in Lemma \ref{newlemma0}, all the newly added edges in $H$ after augmenting the path $P$ in $G$ are level respecting. Moreover, some of the edges which existed before augmentation may be removed from $H$. Destroying an edge in $H$ can only potentially increase the layer number of vertices. Since all the newly created edges after augmentation are level respecting with respect to the layer numbers $L(.)$ computed by BFS at the beginning of the phase, the newly formed edges do not create a shorter path to any vertex from $\HSet{B}{F}$. Therefore, if we do a BFS again from $\HSet{B}{F}$ to assign new layer numbers to vertices, the layer numbers would only increase or remain the same.

\end{proof}
\begin{lemma}
\label{auglength}
After augmenting along the projection of a path $\PH$ in $H$, the augmenting paths in the new graph $H$ after augmentation are of length $\geq$ $|\PH|$.
\end{lemma}
\begin{proof}
In Lemma \ref{layering}, we showed that the layer numbers assigned by BFS to all vertices including vertices in $\HSet{A}{F}$ can only increase or remain the same after augmenting along the projection of path $\PH$. All vertices in $\HSet{A}{F}$ had layer number $|\PH|$ before augmenting the projection of $P'$. After augmentation, using Lemma \ref{layering}, we can infer that the length of shortest path to vertices in $\HSet{A}{F}$ from any vertex in $\HSet{B}{F}$  can only increase or remain same. Thus all the  remaining augmenting paths have length $\geq |\PH|$.
\end{proof}
\paragraph{}
We showed in Lemma \ref{layering} that layer number of all vertices can only increase or remain the same after augmentation. Using Lemma \ref{norepeat} and Lemma \ref{visited}, we show that any vertex which is visited by the FINDAUGPATH procedure in the current phase can be discarded and need not be visited by FINDAUGPATH again. Lemma \ref{visited} shows why this is true for any vertex which is visited but did not lead to a shortest length augmenting path. Lemma \ref{norepeat} shows that we can also discard vertices which participated in an augmenting path in the current phase as they will not be part of any other augmenting path of the shortest length discovered in the same phase by FINDAUGPATH. 
\paragraph{}
Let $S(v)$ indicates the shortest path length from any vertex in $\HSet{B}{F}$ to $v$. At the beginning of each phase, $S(v) = L(v)$ which is assigned by BFS. If we construct a graph $H'$ from $H$ by reversing all the edges in $H$ and then do BFS on $H'$ starting from $\HSet{A}{F}$ vertices at layer 0, then we can make a similar argument that the shortest distance to any vertex $v$ from $\HSet{A}{F}$ (or shortest distance from $v$ to  $\HSet{A}{F}$ in $H$), denoted by $S'(v)$ increases or remains the same after an augmentation.
\paragraph{}
The length of the shortest augmenting path through any vertex $v$ can be represented as sum of the length of shortest path of $v$ from any vertex in $\HSet{B}{F}$ and the length of shortest path from $v$ to any vertex in $\HSet{A}{F}$ i.e. $S(v) + S'(v)$.  Thus for any vertex $v$, if $S(v)$ increases after an augmentation, it will no longer be part of the shortest length augmenting path in the current iteration. Its layer number also increases in the next phase. We have also shown in Lemma \ref{layering} that $S(v)$ can never decrease. This justifies the fact that it suffices to compute BFS layers only once at the beginning of each phase and not after every augmentation. Only those vertices whose $S(.) = L(.)$ would be part of the shortest length augmenting paths in the current phase.
\begin{lemma}
\label{visited}
If a vertex  is marked visited by FINGAUGPATH but did not lead to  a shortest length augmenting path, then it can not be part of any shortest length augmenting path discovered later in the same phase.
\end{lemma}
\begin{proof}
Consider a vertex $z$ which was explored in the current phase by FINDAUGPATH but did not lead to a shortest length ($|P'|$) augmenting path in the current phase. Let $S(z) = i$. Since $z$ was explored in the FINDAUGPATH and no augmenting path of length $|\PH|$ was found, it implies $S'(z) > (|\PH| - i)$. This implies that even if $S(z)$ remains the same after augmenting a path $\PH$, we still have $S(z) + S'(z) > |\PH|$. 
\begin{figure}[!ht]
\centering
\includegraphics[width=0.3\textwidth]{./images/lemma7.png}
\caption{If $z$ is marked visited by partial DFS from $b_1$, $P_1$ is found before $P_2$.}
\label{fig:lemma7}
\end{figure}
\paragraph{}
Alternatively, we can prove this by contradiction. Let us assume that vertex $z$ was marked as visited by FINDAUGPATH routine while doing a partial DFS from $b_1 \in \HSet{B}{F}$, but was not part of a shortest length augmenting path. This implies $S'(z) > |P'|-i$. Later, FINDAUGPATH finds an augmenting path from $b_2 \in \HSet{B}{F}$ to $a \in \HSet{A}{F}$ through $z$ which implies $S'(z) = |P'|-i $. This leads to a contradiction as depicted in Figure \ref{fig:lemma7}. Since $S'(z)$ cannot reduce, the path from $z$ to $a$ should have existed even during partial DFS from $b_1$ and an augmenting path $P_1$ would have been found the first time $z$ was visited before $P_2$ was discovered. This proves the lemma.
\end{proof}
\begin{lemma}
\label{norepeat}
No boundary vertex will be part of two or more augmenting paths of the same length in $H$.
\end{lemma}
\begin{proof}

To prove this lemma, we will show that for a vertex $v$ which is part of augmenting path $\PH$, after augmenting along the projection of $\PH$, has at least one of $S(v)$ or $S'(v)$ increasing which means that the next shortest augmenting path through $v$ will have a length $> |\PH|$.
\paragraph{}
The case where $S(v)$ increases after augmenting $\PH$ is trivial as this implies that $S(v) + S'(v)$ is now greater than $|\PH|$, the length of the shortest augmenting path in the current phase.
\paragraph{}
Let us consider the case where $S(v)$ doesn't change after an augmentation. In this case, we will show that $S'(v)$ should increase. For the sake of contradiction, let us assume that $S'(v)$ does not increase.
Let $(u,v)$ be the edge of the augmenting path $P'$ which was just augmented. Let the projection of $(u,v)$ be $\{u,p_1,p_2,\ldots,p_l,v\}$. Let the new edge responsible for maintaining the same layer number of $v$ be $(u',v)$. This edge could be formed after augmenting the projection of $P'$ or may have existed before. If the edge $(u',v)$ existed before, its projection after augmentation has to be edge-disjoint from the projection of $(u,v)$ before augmentation implying that $v$ has 2 incoming edges in $G_M$. If the edge $(u',v)$ was formed after augmentation, its projection $\{u',p'_1,p'_2,\ldots,p'_l,v\}$ may use some of the reversed edges of projection of $(u,v)$ but the final edge $(p'_l,v)$ in projection of $(u',v)$ would still be different from final edge $(p_l,v)$ in the projection of $(u,v)$. In this case too, we can see that $v$ has at least 2 incoming edges in $G_M$.
\begin{figure}[!ht]
\centering
\includegraphics[width=0.5\textwidth]{./images/Disjoint.pdf}
\caption{If $S(u)$ remains same after augmentation, v has to be of type $A$. }
\label{fig:Disjoint}
\end{figure}
\paragraph{}
We know that in a bipartite matching, any vertex in $B$ has at most 1 incoming edge and every vertex in $A$ has at most 1 outgoing edge in $G_M$. Since vertex $v$ has at least 2 incoming edges in $G_M$, it means $v \in A$ and has only one outgoing edge in $G_M$. $v$ can have many outgoing edges in $H$ all of which share a common edge in their projections on $G_M$. Reversing the projection of any one of the outgoing edges from $v$ in $H$ during augmentation, invalidates all other outgoing edges from $v$ in $H$ (See Figure \ref{fig:Disjoint}). So, $v$ can only have a path to a free vertex in $\HSet{A}{F}$ through a vertex $z$ which had layer number $L(z) < L(v)$ before augmenting the projection of $\PH$. Since $S'(z) > S'(v)$, the second augmenting path through $v$ has length $> |\PH|$.
\end{proof}
\begin{lemma}
\label{I1}
Length of the shortest augmenting paths in $H$ during the $(i+1)^{th}$ iteration is at least 1 greater than the shortest augmenting path in $i^{th}$ iteration.
\end{lemma}
\begin{proof}
The shortest length of an augmenting path in $H$ after running Hopcroft-Karp algorithm in each region is at least 2. Let $\mathcal{L}$ be the length of the shortest augmenting path at the beginning of a given phase. By Lemma \ref{visited} and \ref{norepeat}, after augmenting a path of length $\mathcal{L}$, any remaining augmenting paths of the same length would use unvisited vertices except for possibly the first and last vertices which could be internal vertices. We have also shown in Lemma \ref{auglength} that the length of any new augmenting path created in $H$ after each augmentation because of the newly added edges is greater than or equal to $\mathcal{L}$. Lets say we do a partial DFS from a free vertex $b_1 \in \HSet{B}{F}$ and it did not lead to an augmenting path of length $\mathcal{L}$. Our algorithm continues to do partial DFS from the remaining free vertices in $\HSet{B}{F}$. Lets assume that a new augmenting path $P''$ of length $\mathcal{L}$ is created from $b_1$ because of augmenting along some augmenting path discovered later in the phase. Since our algorithm does not repeat partial DFS from $b_1$, $P''$ may be missed which contradicts our lemma. However,  we can show that $P''$ cannot be created in the first place as it would mean $S'(b_1)$ which was greater than $\mathcal{L}$ initially has become equal to $\mathcal{L}$ which is not possible as we showed in Lemma \ref{layering} and \ref{norepeat}. Therefore, all augmenting paths of length $\mathcal{L}$ are exhaustively found in the given iteration. The minimum length in the next iteration of merge algorithm is at least $\mathcal{L}+1$.
\end{proof}
\subsection{Proof of Invariant}
\paragraph{}
While running the Hopcroft-Karp style algorithm on $H$, we maintain the following invariant.
\begin{lemma}
\label{simplepath}
Let $\PH$ be an augmenting path reported by FINDAUGPATH and let $P$ be its projection on $G_M$. Then $P$ is a simple path.
\end{lemma}
\begin{proof}
\begin{figure}[!ht]
\centering
\includegraphics[width=0.8\textwidth]{./images/Simplepath.PNG}
\caption{Projection of $2$ edges of augmenting path in $H$ cannot intersect in $G$}
\label{fig:Simplepath}
\end{figure}
By construction, $\PH$ is a simple path. For the sake of contradiction, let us assume that there are at least two edges $(u,v)$ and $(u^{\prime},v^{\prime})$ in $\PH$ whose projections intersect. Without loss of generality, let $u^{\prime}$ come later in the path $\PH$. So, $\layer{u^{\prime}} \geq$  $\layer{u}+1$. Moreover, FINDAUGPATH chooses edges such that $\layer{v} = \layer{u}+1$ and $\layer{v^{\prime}} = \layer{u^{\prime}}+1$. Let $P_{uv}$ and $P_{u^{\prime}v^{\prime}}$ be the projections of the 2 edges. Since the projections intersect in $G_M$, the projections are in the same region $R_j$ and share a common edge, say $(w,x)$. This is because $w$ cannot have multiple incoming and multiple outgoing edges in a bipartite graph. This gives us the condition that $\layer{v'} \geq \layer{u}+3$. $P_{uv}$ is a directed path from $u$ to $v$ through $w$ in the region $R_j$ of $G_M$ and $P_{u^{\prime}v^{\prime}}$ is a directed path from $u^{\prime}$ to $v^{\prime}$ through $w$ in the same region. This means that there is also a directed path from $u$ to $v^{\prime}$ and by construction of $H$, there would have been an edge from $u$ to $v'$ in $H$. By BFS labeling, $\layer{v^{\prime}} \leq \layer{u}+1$. This contradicts with our earlier condition that $\layer{v^{\prime}} \geq \layer{u}+3$. Therefore, our assumption that projections of 2 edges intersect is incorrect. Since no projections intersect, there cannot be a cycle in $P$ and it is a simple path. 
\end{proof}
\section{Algorithm Efficiency}
\label{Algo Efficiency}

\begin{lemma}
\label{lem:iterations}
	After $\sqrt[]{|V_H}|$ iterations of the algorithm, there will be at most $O(\sqrt[]{|V_H}|)$ unmatched nodes remaining.
\end{lemma}
\begin{proof}
From lemma \ref{I1}, length of augmenting path in $H$ grows by at least 1 after every iteration. After $\sqrt[]{|V_H}|$ iterations, length of augmenting path in $H$ is at least $\sqrt[]{|V_H|}+2$ with at least $(\sqrt[]{|V_H}|)$ boundary vertices. Since we eliminated augmenting paths within each region as part of preprocessing before running the  Hopcroft-Karp style algorithm, the remaining augmenting should span multiple regions. This implies that all augmenting paths in $H$ contain at least one boundary vertex. 
\paragraph{}
We know that that symmetric difference of the optimal matching $M^*$ and the matching $M$ after $\sqrt[]{|V_H}|$ iterations will form a set of vertex-disjoint augmenting paths in $G_M$. By Lemma \ref{disjoint}, these paths map to paths in $H$ which are vertex disjoint in $H$ except for the first and the last vertex. Thus the bound on vertex-disjoint augmenting paths in $G$ can be found by bounding vertex-disjoint augmenting paths in $H$ excluding the first and last vertex. There are  $O(V_H)$ boundary vertices in total. From Lemma \ref{I1} and Lemma \ref{disjoint}, the number of such vertex-disjoint augmenting paths in $H$ after $(\sqrt{V_H})$ iterations is bound by $O(V_H)/(\sqrt[]{|V_H}|)$ = $O(\sqrt[]{|V_H}|)$ thus proving the lemma.
\end{proof}
\subsection{Efficiency of BFS, FINDAUGPATH and AUGMENT procedures}
\paragraph{}
 The layered graph can be constructed with a single BFS in $O(n)$ time. However, section \ref{FastBFS} presents a way to accomplish this in $O(|V_H|\log^{2}{n})$ time, that is $O(\frac{n}{\sqrt[]{r}}\log^2{n})$.
\paragraph{}
Let ${P_i'}$ be the $i^{th}$ augmenting path in $H$ computed by FINDAUGPATH procedure. For an edge in ${P_i'}$ belonging to $\RH{j}$, computing its projection in $G_M$ using only the edges in $R_j$ takes $O(r)$ time. Computing the new edges in each affected partition of $H$ can be done by recomputing the dense distance graph for the partition and querying it. Dense distance graph construction takes $O(r\log^{3}{r})$ as described by Fakcharoenphol and Rao \cite{frao}. The number of affected partitions identified by the AUGMENT procedure is at most $\Delta$ = $\sum_i |P_i'|$. Therefore, the total time taken by AUGMENT procedure is $O(r\Delta\log^{3}{r})$. Lemma \ref{delta}  bounds $\Delta$ by $O(|V_H|\log{n})$. Therefore, total time taken by AUGMENT procedure is $O(r|V_H|\log^{3}{r}\log{n})$
\paragraph{}
Before an augmenting path is found, each edge in $H$ is explored only once by FINDAUGPATH and there are $O(r)$ edges in  each region $\RH{j}$ making it $O(n)$ across all regions in $H$. After each augmentation, the time taken to compute new edges in affected partitions can be taxed to the complexity of AUGMENT procedure. Therefore, the  complexity of FINDAUGPATH is $O(n)$. In the next chapter, we show how this bound can be improved to $O(\frac{n}{\sqrt[]{r}}\log^{2}{n})$ which is proportional to the total number of vertices in $H$ instead of number of edges in $H$.
\begin{lemma}
\label{delta}
Let $\mathbb{P}$ be the set of all augmenting paths in $H$ generated by the FINDAUGPATH procedure. Then,
$$\Delta = \sum_{\PH \in \mathbb{P}} |\PH| = O(|V_H|\log{n})$$
\end{lemma}
\begin{proof}
  Let $P_i'$ be the $i^{th}$ augmenting path generated by the FINDAUGPATH procedure. Consider the matching $M_{i-1}$ in $G$ before augmenting along projection of $P_i'$ and let $M^*$ be an optimal matching. $M_{i-1} \oplus M^*$ has a degree at most 2 and therefore forms a set of disjoint paths and cycles in $G$. These paths/cycles translate to disjoint paths/cycles in $H$ as shown in Lemma \ref{disjoint} except for the start and the end vertices if they happen to be internal $b_j$ or $a_j$.  Let $\overrightarrow{\mathcal{P}}$ be the set of paths in $M_{i-1} \oplus M^*$ and let $\PathsH{}$ be the set of paths in $\overrightarrow{\mathcal{P}}$ lifted to $H$. Our algorithm ensures that each augmenting path ${\PH_{i}}$ found in $H$ is a minimum length path, but the minimum length of $\PH_{i}$ is unclear. Instead, we can use the average length of all paths in $\PathsH{}$ as an upper bound on the length of $\PH_{i}$. We know that there are $O(\sqrt{n})$  augmenting paths at the beginning of the merge step. Before $i^{th}$ augmentation, the number of augmenting paths remaining  is $k\sqrt{n}-i+1$ where $k$ is some constant.
  \paragraph{} 
  The average length of $(i)^{th}$ augmenting path in $H$ would be \[ O(|V_H|)/(k\sqrt{n}-i+1)\] where $O(V_H)$ is the total number of edges in $\PathsH{}$ as there are $O(|V_H|)$ boundary vertices with degree equal to 2 in $\PathsH{}$.
 To bound the total length of all augmenting paths in $H$, we sum the average length of $i^{th}$ augmenting path over all values of i from 1 to $k\sqrt{n}$ which gives $$\sum_{i=1}^{k\sqrt{n}}O(|V_H|)/(k\sqrt{n}-i+1) = O(|V_H|)\sum_{i=1}^{k\sqrt{n}}1/(k\sqrt{n}-i+1)$$ Substituting $(k\sqrt{n}-i+1)$ by $i^{\prime}$, we get $$O(|V_H|)\sum_{i=1}^{k\sqrt{n}}1/(k\sqrt{n}-i+1) = O(|V_H|)\sum_{i^{\prime}=1}^{k\sqrt{n}}1/i^{\prime}$$. \(\sum_{i^{\prime}=1}^{k\sqrt{n}}1/i^{\prime}\) is the $(k\sqrt{n})^{th}$ harmonic number which can be bounded by $\theta(\log{(k\sqrt{n}}))$. Therefore, $$\Delta \leq O(|V_H|)\sum_{i^{\prime}=1}^{k\sqrt{n}}1/i^{\prime} = O(|V_H|\log{n})= O((n/\sqrt[]{r})\log{n}) $$. 
\end{proof}
\paragraph{}
By choosing $r=n^{2/3}$, we get the overall time taken by AUGMENT procedure to be $O(r|V_H|\log^{3}{r}\log{n}) = O(n^{4/3}\log^{4}{n})$. BFS and FINDAUGPATH take $O(n)$ per iteration and there are $O(\sqrt{V_H})$ iterations in total, which results in total time of $O(n^{4/3})$ for these two operations together. Therefore, the overall complexity of the merge step of our algorithm is $O(n^{4/3}\log^{4}{n})$. We can reduce the power on $log$ term from 4 to 2 by using Klein's MSSP data structure \cite{klein2005} or Thorup's connectivity oracle \cite{thorup} for reconstruction of edges of $H$. In Chapter 4, we will show that the overall run time can be improved further by using faster BFS and FINDAUGPATH implementations along with a wise choice of $r$ for r-division.
\section{Hopcroft-Karp Equivalence of Our Algorithm}
From our proofs, it can be observed that our algorithm is very similar to the traditional Hopcroft-Karp algorithm except that it runs on $H$ instead of $G$. The similarity can be summarized as follows.
\begin{itemize}
   \item  We compute BFS layers only once at the beginning of each iteration [Lemma \ref{layering}, \ref{auglength}, \ref{norepeat}].
   \item  We find vertex disjoint shortest length augmenting paths in $H$ except for maybe the first and the last vertex.[Lemma \ref{norepeat}, \ref{visited}].
   \item  The length of the shortest augmenting path in $H$ grows every iteration [Lemma \ref{I1}].
   \item Total number of iterations of our algorithm is $O(\sqrt{|V_H|})$ where $V_H$ refers to set of vertices in $H$ and $|V_H| = O(n/\sqrt{r})$ [Lemma \ref{lem:iterations}]. Hopcroft-Karp algorithm takes $\sqrt{|V|}$ iterations where $V$ refers to set of vertices in $G$ and $|V| =n$.
   \item We bound the total length of all augmenting paths in $H$ to be $O(|V_H|\log{n})$ [Lemma \ref{delta}]. Hopcroft-Karp algorithm bounds the total length of all augmenting paths in $G$ to be $O(n\log{n})$.
\end{itemize}
