\chapter{Introduction}
\markright{Mudabir Kabir Asathulla \hfill Chapter 1. Introduction \hfill}
\paragraph{}
Matching theory is a widely studied area since the beginning of the twentieth century and has applications spanning diverse fields involving large scale resource allocation. Some of the classic examples of matching as stated in the survey by Gerards \cite{gerards} are $\textit{the assignment problem}$, $\textit{The oil well drilling problem}$ \cite{devine}, $\textit{plotting street maps}$ (\cite{iri1980determination},\cite{iri1983heuristics}) and $\textit{scheduling}$ \cite{fujii1969optimal}.  Matching problems also hold significance in the field of algorithms for several reasons that transcend their practical applications. Edmonds $\&$ Johnson \cite{edmondsjohnson} state that the matching problems can be positioned between the 'easier' problems like network flows and the hard (NP-hard) problems like general integer linear programming. Cunningham $\&$ Marsh \cite{cunningham} state that "Optimum matching problems constitute the only class of genuine integer programs for which a good solution is known". Owing to the significance of matching, hundreds of algorithms have been developed till date and there are still many open problems in this area.
\paragraph{}
$\textit{Matching}$ can be defined as dividing a collection of objects into pairs. Formally, matching $M$ in an undirected graph $G$ with node set $V$ and edge set $E$ can be defined as a subset of edges in $E$ such that no two edges are incident to a common vertex. If all the vertices in $V$ have a pairing in $M$, we call $M$ a $\textit{perfect matching}$. A matching problem consists of the graph $G$ and the edge weights $w$. The $\textit{Maximum Cardinality Matching}$ problem is an easier problem with unit edge weights. Besides its own applications, maximum cardinality matching is often used as a subroutine for solving weighted matching problem, thus making it a compelling problem to study. If the graph $G$ is bipartite, which is the case in many practical applications, we call it $\textit{bipartite matching}$. 
\paragraph{}
In our work, we present an algorithm to find maximum cardinality bipartite matching in a specific class of graphs called $\textit{planar graphs}$. A planar graph is a graph that can be drawn on a plane such that edges don't cross each other and intersect only at their endpoints. A planar graph with $n$ vertices and $m$ edges obeys the property that if $n \geq 3$, then $m \leq 3n-6$ and if there are no cycles of length 3, $m \leq 2n-4$. In other words, planar graphs are sparse. Owing to the simplicity of their structure, planar graphs permit some algorithmic problems to be solved more efficiently than arbitrary graphs. For example, Max-cut is an NP-Complete problem for arbitrary graphs but has a polynomial time solution in the planar setting. In addition to being structurally simple, planar graphs are encountered in many real life situations like electronic circuit layouts, image processing, building construction plans, traffic maps etc., serving as a motivation to design faster algorithms specific to planar graphs.

\section{Preliminaries}
\paragraph{}
In this section, we will introduce some basic notations and definitions related to maximum cardinality bipartite matching henceforth referred to as bipartite matching.

\begin{figure}[!ht]
\centering
\includegraphics[width=0.6\textwidth]{./images/Figure1.png}
\caption{Bipartite Graph and its Residual Graph}
\label{fig:fig1}
\end{figure}

\paragraph{}
Consider a bipartite graph $G(A \cup B,E)$ with two disjoint vertex sets $A$ and $B$ and edges $E$ between them as shown in Figure $\ref{fig:fig1}$. The thick edges are part of partial matching $M$ while other edges are not in the matching. The graph on the right is the $\textit{residual graph}$ $G_M$ where all edges in the matching $(E \cap M)$ are directed from $a \rightarrow b$ and all the other edges that are not in the matching are directed from $b \rightarrow a$. The residual graph is widely used for computing flows in a network. Bipartite matching is a special instance of network flow and $G_M$ is the residual graph for this instance. Given a partial matching $M$, we define the $\textit{alternating path}$ as any path in the graph $G$ which alternates between edges in the matching ($E \cap M$) and edges that are not in the matching ($E \backslash M$). It is easy to see that any directed path in $G_M$ is an alternating path in $G$. Similarly, an $\textit{alternating cycle}$ can be defined. An alternating path $\Path$ between two free (unmatched) vertices  is called an $\textit{augmenting path}$. We can $augment$ the matching $M$ by one edge along $P$ if we remove the edges of $\Path \cap M$ from $M$ and add edges of $\Path \backslash M$ to $M$. After augmentation, the new matching is given by $M \leftarrow M \oplus P$, where $\oplus$ is the symmetric difference operator. BFS/DFS can be used to find an augmenting path in the residual graph and each augmentation increases the size of the matching $|M|$ by 1. Most matching algorithms start with an empty matching and iteratively augment the matching until a maximum matching is reached. When there are no augmenting paths left in the residual graph, the matching is said to be $\textit{maximum matching}$. We state an important property of augmenting paths which was proved by Berge \cite{berge}.
\begin{theorem}
\label{th:berge}
A matching M in a graph G is a maximum matching if and only if there is no augmenting path with respect to M in G.
\end{theorem}

\section{Previous Work}
\paragraph{}
Major breakthroughs in bipartite matching began in the mid 50's. Ford and Fulkerson came up with the first polynomial time algorithm \cite{ford1956maxflow} for maximum flow problem in a single-source, single-sink flow network. In 1962, Ford and Fulkerson showed in their book \cite{ford} that maximum cardinality bipartite matching problem in an arbitrary graph can be reduced to a  maximum flow problem in a single-source, single-sink flow network. Given a bipartite graph $G(A\cup B,E)$ and its residual graph $G_M$, we can construct a flow network $G'(s,t,c)$ from $G_M$ by introducing a source vertex $s$ and a sink vertex $t$ and adding directed edges from $s$ to all vertices of type $B$ and also from all vertices of type $A$ to $t$. The resulting flow network has unit edge capacities $(c=1)$. Ford and Fulkerson showed that maximum flow $f$ in $G'$ is equal to the size of the maximum matching $|M|$ in $G$ and that max-flow residual graph of $G'$ can be used to reconstruct maximum matching $M$ in $G$.
\paragraph{}
Given a bipartite graph $G$ with $m$ edges and $n$ vertices, Ford-Fulkerson algorithm runs $O(n)$ iterations of DFS where each DFS operation finds one augmenting path and has a run time of $O(m)$. Thus, the overall run time of the algorithm is $O(mn)$. Edmond and Karp's max-flow algorithm \cite{edmonds} and few other max-flow algorithms developed later could also solve the bipartite matching by reducing it to network flow problem. Their complexity for computing maximum matching is also $O(mn)$. 
\paragraph{}
Hopcroft-Karp algorithm \cite{hopcroft} introduced in 70's with a running time of $O(m\sqrt{n})$ remains the best combinatorial algorithm (based on augmenting paths) for bipartite matching in arbitrary graphs till date. It improves upon Ford-Fulkerson algorithm by finding a maximal set of vertex-disjoint shortest length augmenting paths in each iteration instead of just one augmenting path per iteration. Hopcroft-Karp algorithm uses a combination of BFS and DFS to find maximal set of augmenting paths in each iteration and it requires $O(\sqrt{n})$ iterations (section \ref{HK revisited}) to compute maximum matching. 
\paragraph{}
In 2004, Mucha and Sankowski presented a randomized algorithm based on fast matrix multiplication  \cite{mucha} which gives $O(n^\omega)$ complexity ($\omega = 2.376$) for maximum cardinality matching in both bipartite and general graphs. This algorithm uses a Gaussian elimination approach and has the best run time in arbitrary graph settings till date.
\paragraph{}
Since planar graphs are sparse with $m$ being $O(n)$, the complexities of Ford-Fulkerson algorithm and  Hopcroft-Karp algorithm in planar graph setting become $O(n^2)$ and  $O(n^{3/2})$ respectively. Mucha and Sankowski also came up with an improved randomized algorithm in planar setting \cite{muchaplanar} with $O(n^{\omega/2})$ time complexity. Just like their algorithm for arbitrary graphs \cite{mucha}, this algorithm again works for both bipartite and general matching and is based on Gaussian elimination approach.
\paragraph{}
Lipton and Tarjan's planar separator theorem \cite{lipton} paved way to devise \textrevapostrophe divide and conquer' algorithms \cite{liptonapp} for planar graphs. Planar separator theorem states that by removing $O(\sqrt{n})$ vertices ($\textit{separator vertices}$) from a $n$-vertex planar graph, we can partition the graph into two edge disjoint sub-graphs each with at most $\frac{2n}{3}$ vertices. Given the maximum matching in each sub-graph, the maximum matching in the original graph is computed by introducing the $O(\sqrt{n})$ separator vertices. Using Ford-Fulkerson algorithm in the $conquer$ step of the divide and conquer approach, we can find maximum matching in $O(n^{3/2})$ time (section \ref{Overview}) which is the same complexity as Hopcroft-Karp algorithm. 
\paragraph{}
Klein et al. \cite{klein1994} were able to give $O(n^{4/3}\log{n})$ time algorithm for finding a maximum matching in bipartite planar graphs using the reduction of maximum flow with multiple sources and sinks to a single source shortest paths problem. In 2012, Borradaile et al. \cite{borradaile} came up with $O(n\log^{3}{n})$ time algorithm for the max-flow with multiple sources and sinks (single-source and sink reduction does not preserve planarity), thus also providing the first near linear time solution for finding a maximum matching in bipartite planar graphs.

\section{Our Contributions}
\paragraph{}
We present a new sparsification based approach to find a maximum matching in planar bipartite graphs. Our algorithm finds a maximal set of vertex-disjoint shortest length augmenting paths similar to Hopcroft-Karp algorithm and uses a \textrevapostrophe divide and conquer' approach similar to Lipton-Tarjan algorithm. By combining these features and by exploiting planar graph properties, our algorithm performs faster than either of the above matching algorithms which take $O(n^{3/2})$ time individually. 
\paragraph{}
It is known that we can use planar separators to partition an  n-vertex planar graph $G$ into $O(n/r)$ edge disjoint pieces, each of size $O(r)$ where $r < n$.  This decomposition is referred to as $r$-division (\cite{federickson},\cite{kleintree}). In addition, $r$-division (section \ref{r-division}) guarantees that each piece has only $O(\sqrt{r})$ vertices that participate in other pieces and such vertices are called boundary vertices. Therefore, in total, there are $O(n/\sqrt{r})$ boundary vertices. 
\paragraph{}
We use Lipton-Tarjan \textrevapostrophe divide and conquer' approach in our algorithm (section \ref{Overview}). At the beginning of the conquer/merge step of our algorithm, we are left with $O(\sqrt{n})$ augmenting paths. As a part of pre-processing in our merge algorithm, we perform $r$-division of our graph $G$ and then find maximum matching in each each piece of $G$ by running the Ford-Fulkerson algorithm in each piece. From the resulting residual graph $G_M$, we construct a compressed residual graph $H$ from the boundary vertices of our $r$-division and unmatched internal vertices (not a boundary vertex) of each piece. $H$ has $O(n/\sqrt{r})$ vertices and $O(n)$ edges as we will see in Section \ref{Construction of H}. After constructing $H$, we run a Hopcroft-Karp style algorithm on $H$ instead of actual graph $G$ to obtain the speed up. 
\paragraph{}
Using fast implementations of BFS and DFS, we are able to speed up each iteration of our algorithm.  We also reduce the number of iterations from $O(\sqrt{n})$ to $O(\sqrt{n}/r^{1/4})$ which is in the order of square root of number of vertices in $H$ or number of boundary vertices in $G$, thus making the algorithm terminate faster. However, we cannot sparsify our graph beyond a limit as choosing a large value for $r$ would increase the number of vertices in each region of $r$-division. After each augmentation, the residual graph $G_M$ changes and as result, the compressed residual graph $H$ changes. We need to reconstruct the edges of $H$ in all the pieces that contributed an edge to the augmenting path. Total time spent in reconstructing $H$  throughout the algorithm is directly proportional to $O(n\sqrt{r})$ as we will see in Chapter \ref{chapter3}. By carefully choosing $r$ to balance both competing factors namely (BFS + DFS + Number of iterations) and (reconstruction of $H$), we come up with $\sixfive$ time algorithm (Chapter \ref{chapter4}). The $\sim$ above $O$ represents poly(log) term. Though our algorithm is not the fastest (\cite{borradaile},\cite{muchaplanar}), the sparsification approach for bipartite matching is novel and may potentially be extended to other matching problems in planar and non-planar graphs.

\section{Thesis Outline}
\paragraph{}
The rest of the thesis is organized as follows: We introduce the background, notations, and describe planar graph oracles/data structures used in the construction of compressed  residual graph and for fast implementations of BFS/DFS in Chapter \ref{chapter2}. We introduce our algorithm in Chapter \ref{chapter3} and we present the details of a simpler version of our algorithm which runs in $\fourthree$ time. Chapter \ref{chapter3} also covers the proof of correctness of our algorithm. At the end of the chapter, we highlight the similarity of our algorithm with the Hopcroft-Karp algorithm. In Chapter \ref{chapter4}, we describe the faster BFS implementation in planar graphs which helps speed up the algorithm to $\fivefour$. We also describe a faster DFS technique which when combined with faster BFS implementation along with the right selection of $r$ for $r$-division yields $\sixfive$ time complexity. We conclude and state future work in Chapter \ref{conclusion}.
