\documentclass[11pt]{article}
\usepackage{amssymb}
\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{epsfig}
\usepackage[matrix,graph]{xy}
\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{prop}[theorem]{Proposition}
\newcommand{\qed}{\rule{7pt}{7pt}}
\newenvironment{proof}{\noindent{\bf Proof:}}{\qed\bigskip}
\newenvironment{proof_of_claim}{\noindent{\bf Proof of Claim:}}{\qed\medskip}
\newcommand{\mycount}{{\cal C}}
\newcommand{\Fmp}{\mbox{$\mathbb{{\cal FPM}}(G)$}}
\newcommand{\PMp}{\mbox{$\mathbb{{\cal PM}}(G)$}}
\newcommand{\Mp}{\mbox{$\mathbb{{\cal M}}(G)$}}
\newcommand{\Srch}{\mbox{{\sc search-PM}}}
\newcommand{\Cnt}{\mbox{{\sc count-PM}}}
\newcommand{\BCnt}{\mbox{{\sc bit-count-PM}}}
\newcommand{\eqnslab}[1]{\label{eqn:#1}}
\newcommand{\figlab}[1]{\label{fig:#1}}
\newcommand{\factlab}[1]{\label{fact:#1}}
\newcommand{\proplab}[1]{\label{prop:#1}}
\newcommand{\lemlab}[1]{\label{lemma:#1}}
\newcommand{\theolab}[1]{\label{theo:#1}}
\newcommand{\corlab}[1]{\label{cor:#1}}
\newcommand{\seclab}[1]{\label{sec:#1}}
\newcommand{\subseclab}[1]{\label{subsec:#1}}
\newcommand{\clalab}[1]{\label{claim:#1}}
\newcommand{\deflab}[1]{\label{definition:#1}}
\newcommand{\eqnsref}[1]{Equations~\ref{eqn:#1}}
\newcommand{\figref}[1]{Figure~\ref{fig:#1}}
\newcommand{\propref}[1]{Proposition~\ref{prop:#1}}
\newcommand{\factref}[1]{Fact~\ref{fact:#1}}
\newcommand{\lemref}[1]{Lemma~\ref{lemma:#1}}
\newcommand{\theoref}[1]{Theorem~\ref{theo:#1}}
\newcommand{\corref}[1]{Corollary~\ref{cor:#1}}
\newcommand{\secref}[1]{Section~\ref{sec:#1}}
\newcommand{\subsecref}[1]{Section~\ref{subsec:#1}}
\newcommand{\remref}[1]{Remark~\ref{rem:#1}}
\newcommand{\defref}[1]{Definition~\ref{definition:#1}}
\bibliographystyle{abbrv}
\begin{document}
\title{Some perfect matchings and perfect
half-integral matchings in NC\footnote{Most
results in this paper were originally announced in papers in
Proc.\ 32nd ACM Symposium on Theory of Computing (2000) \cite{MV-STOC00}
and
Proc.\ 12th European Symposium on Algorithms (2004) \cite{KM04}.}
}
\author{
Raghav Kulkarni\thanks{Parts of this work were done when this author was
at the Chennai Mathematical Institute, and while visiting the
Institute of Mathematical Sciences, Chennai.} \\
Department of Computer Science\\
University of Chicago \\
Chicago, USA \\
Email: {\tt raghav@cs.uchicago.edu}
\and
Meena Mahajan\thanks{Part of this
work was done when this author was supported by the NSF grant
CCR-9734918 on a visit to Rutgers University, USA.}\\
The Institute of Mathematical Sciences\\
Chennai 600 113, India\\
Email: {\tt meena@imsc.res.in}
\and
Kasturi R. Varadarajan\thanks{Parts of this work were
done when this author was at DIMACS, Rutgers University, USA and then
at the Tata Institute of Fundamental Research, Mumbai, India.}\\
Department of Computer Science\\
The University of Iowa\\
Iowa City, IA 52242-1419 USA\\
Email: {\tt kvaradar@cs.uiowa.edu}
}
\maketitle
\begin{abstract}
We show that for any class of bipartite graphs which is closed under
edge deletion and where the number of perfect matchings can be
counted in NC, there is a deterministic NC algorithm for finding a
perfect matching. In particular, a perfect matching can be found in
NC for planar bipartite graphs and $K_{3,3}$-free bipartite graphs
via this approach. A crucial ingredient is part of an interior-point
algorithm due to Goldberg, Plotkin, Shmoys and Tardos.
An easy observation allows this approach to handle
regular bipartite graphs as well.
We show, by a careful analysis of the polynomial time algorithm due
to Galluccio and Loebl, that the number of perfect
matchings in a graph of small ($O(\log n)$) genus can be counted in
NC. So perfect matchings in small genus bipartite graphs can also be
found via this approach.
We then present a different algorithm for finding a perfect matching
in a planar bipartite graph. This algorithm is substantially
different from the algorithm described above, and also from the
algorithm of Miller and Naor, which predates the approach of
Goldberg {\it et al.} and tackles the same problem. Our new algorithm extends
to small genus bipartite graphs, but not to $K_{3,3}$-free bipartite
graphs. We next show that a non-trivial extension of this algorithm
allows us to compute a vertex of the fractional perfect matching
polytope (such a vertex is either a perfect matching or a
half-integral matching) in NC, provided the graph is planar or small
genus but {\em not necessarily bipartite}, and has a perfect
matching to begin with. This extension rekindles the hope for an
NC-algorithm to find a perfect matching in a non-bipartite planar
graph.
\end{abstract}
\section{Introduction}
\seclab{intro} The perfect matching problem is of fundamental interest
in combinatorics, algorithms and complexity theory for a
variety of reasons. In particular, the problems of deciding if a graph
has a perfect matching, and finding such a matching if one exists,
have received considerable attention in the field of parallel
algorithms. (See for instance \cite{Vazbook,KarpinskiRytter}.) Both
these problems are in randomized NC \cite{Lovasz,KUW,MVV} but are not
known to be in deterministic NC. For special classes of graphs,
however, there are deterministic NC algorithms.
The outstanding open problem here is to give a deterministic NC
algorithm for detecting/searching for a perfect matching in a given
graph. Some progress in this direction was achieved with two sublinear
time parallel algorithms for bipartite matching: $O(n^{2/3}\log^3n)$
due to Goldberg, Plotkin and Vaidya \cite{GPV}, and $O(m^{1/2}\log^3 n)$
due to Goldberg, Plotkin, Shmoys and Tardos \cite{GPST}. NC algorithms have
been obtained for some special classes of graphs; for instance, dense
graphs (minimum degree at least $n/2$) \cite{DHK}, regular bipartite
graphs \cite{LPV}, strongly chordal graphs \cite{DK}, graphs with
polynomially bounded number of perfect matchings \cite{GK}, $P_4$-tidy
graphs\cite{Parfenoff}, convex bipartite graphs \cite{DS},
incomparability graphs \cite{KVV}, claw-free graphs \cite{CNN}, and
planar bipartite graphs \cite{MillerNaor}.
The problem of counting perfect matchings in a given
graph is $\#$P-hard \cite{val79}, and a polynomial time algorithm is
therefore unlikely for it. Again, for special classes of graphs,
counting is easy; for instance, planar graphs, $K_{3,3}$-free graphs
(graphs that do not contain a subgraph homeomorphic to $K_{3,3}$; this
class of graphs includes all planar graphs),
regular bipartite graphs. The category we are specifically interested
in is planar graphs. A combination of results due to Kasteleyn
\cite{Kastelyn}, Little \cite{little} and Vazirani \cite{Vaz}
establishes that for planar graphs, counting perfect
matchings can be done in P and even in NC. The technique is to
establish that every planar graph has what is called a pfaffian
orientation, one in which every perfect matching gets the same sign
under a suitable signing convention. The signed sum of all perfect
matchings is easy to compute; thus given a pfaffian orientation the
number of perfect matchings can be obtained. Recently, Galluccio and
Loebl \cite{GL-EJC1} extended the results of Kasteleyn to the case of
graphs of small genus. They proved that the generating function of the
perfect matchings of a graph of genus $g$ may be obtained as a linear
combination of $4^g$ pfaffians. This means that one can count
perfect matchings by first finding $4^g$ orientations, and
then taking a linear combination of $4^g$ corresponding
determinants. This gives a polynomial time algorithm for any
$n$-vertex graph graph with $O(\log n)$ genus.
Surprisingly, an NC algorithm for finding a perfect matching in a
planar graph has proved quite elusive. This situation is rather
intriguing, as it contradicts our intuition that search should be
easier than counting. For the case of bipartite planar graphs,
Miller and Naor \cite{MillerNaor} succeeded in giving an NC
algorithm to find a perfect matching. Their method reduces this
problem to that of finding a circulation in the planar graph,
which then corresponds to computing shortest paths in its planar
dual.
We expect the search problem to be easier for classes of bipartite
graphs rather than general graphs because of a fundamental property of
these graphs: the fractional perfect matching polytope \Fmp\ (see
\secref{prelim} for definitions) for bipartite graphs coincides with
the perfect matching polytope \PMp. This breaks down in general
graphs; \PMp\ could even be empty while \Fmp\ is non-trivial. Thus,
for instance, we see no way of extending the algorithm of \cite{MillerNaor},
or even the algorithm of \cite{GPST}, to planar
non-bipartite graphs.
Our contributions are as follows:
\begin{enumerate}
\item We show in \secref{srch-cnt} that for bipartite graphs, search
is not harder than counting. For any class of bipartite graphs where
counting perfect matchings is in NC (and the class is closed under
edge deletion), finding a perfect matching is also in NC. This
result is established using the second part of the algorithm of
\cite{GPST}, and it applies to bipartite graphs that are
$K_{3,3}$-free or regular. To the best of our knowledge, this connection
between counting and the applicability of \cite{GPST} has not been
made before.
\item We show that the number of perfect matchings in a graph of genus
$O( \log |V|)$ can be computed in NC. This is established by
extending the algorithm of Galluccio and Loebl \cite{GL-EJC1}, and
using the algorithm of \cite{MSV04} to compute the pfaffian with its
sign in NC. This result is established in \secref{torus-count}.
\item We give, in \secref{our-algo}, a new NC algorithm for finding a
perfect matching in a planar bipartite graph. This algorithm is
essentially different from that of \secref{srch-cnt}, as well as
from that of \cite{MillerNaor}. It extends to small genus bipartite
graphs as well, though not to $K_{3,3}$-free bipartite graphs.
\item Using the algorithm of \secref{our-algo} as a starting point, we
devise in \secref{halfint} an NC algorithm to find a vertex of the
fractional perfect matching polytope \Fmp\ of a planar, {\em not
necessarily bipartite}, graph. As in the the algorithm of
\secref{our-algo}, this algorithm is also an interior-point
algorithm; it stays within \Fmp\ while navigating towards a
vertex. Using the result of \secref{torus-count}, it extends to
small-genus graphs as well. This is one of the first results of this
flavour - finding the optimum of a linear program instance in NC
when the corresponding integer program is solvable in P. This
algorithm also rekindles the hope of obtaining an NC algorithm for
finding a perfect matching in a planar graph.
\end{enumerate}
\section{Preliminaries}
\seclab{prelim}
\subsection{Matching polytopes}
Let $G$ be a graph with $m$ edges.
Consider the polytope \Fmp\ in $m$-dimensional space,
defined by the following constraints.
\begin{eqnarray}
\eqnslab{fmp}
x_e & \geq & 0 ~~\forall\: e \in E \nonumber \\[2mm]
{\displaystyle \sum_{\mbox{$e$ incident on $v$}}} x_e &=& 1~~\forall\: v \in V
\end{eqnarray}
This polytope is called the fractional perfect matching polytope.
Clearly, every perfect matching of $G$ (i.e.\ the corresponding point
in $\mathbb{\cal Q}^m$) lies in \Fmp. Standard matching theory (see
for instance \cite{LP86}) tells us that every perfect matching of $G$
is a vertex of \Fmp. (A perfect matching is an integral solution to
\eqnsref{fmp}).
In the case of
bipartite graphs, the perfect matchings are in fact the only vertices
of \Fmp; \Fmp\ = \PMp. Thus for a bipartite graph it suffices to find a
vertex of \Fmp\ to get a perfect matching. Furthermore, for general
graphs, all vertices of \Fmp\ are always half-integral (in the set
$\{0,1/2,1\}^m$). For any vertex $w$ of \Fmp , if we pick those edges
of $G$ having non-zero weight in $w$, we get a subgraph which is a
disjoint union of a partial matching and some odd cycles.
For instance, \figref{empty-mp} shows a graph where
\PMp\ is empty, while \Fmp\ has one point shown by the weighted graph
alongside. \figref{vertex-of-fmp} shows a graph where \PMp\ is
non-empty; furthermore, the weighted graph in
\figref{vertex-of-fmp}(b) is a vertex of \Fmp\ not in \PMp.
\begin{figure}[ht]
\begin{minipage}[t]{0.4\linewidth}
\centering
\begin{center}
\epsfxsize=2.5in
\epsfbox{fig-empty-mp.eps}
\end{center}
\caption{An Example Graph with empty $\PMp$, and a point in \Fmp}
\figlab{empty-mp}
\end{minipage}\hfill
\begin{minipage}[t]{0.5\linewidth}
\centering
\begin{center}
\epsfxsize=3in
\epsfbox{fig-vertex-of-fmp.eps}
\end{center}
\caption{An Example Graph with non-empty $\PMp$, and a point in $\Fmp - \PMp$}
\figlab{vertex-of-fmp}
\end{minipage}
\end{figure}
The matching polytope \Mp\ for a graph $G$ is the convex
hull of all matchings (not necessarily perfect) in $G$. All maximal
matchings are vertices of \Mp. If $G$ is
bipartite, then the polytope \Mp\ is also defined by the following
equations.
\begin{eqnarray}
\eqnslab{mp}
x_e & \geq & 0 ~~\forall\: e \in E \nonumber \\[2mm]
\eqnslab{mp2}
{\displaystyle \sum_{\mbox{$e$ incident on $v$}}} x_e
&\le& 1~~\forall\: v \in V
\end{eqnarray}
That is, for bipartite graphs, all vertices of the polytope defined by
\eqnsref{mp} are integral and hence correspond to matchings in $G$.
Thus for bipartite graphs, $\PMp = \Fmp \subseteq \Mp$.
\subsection{Embeddings}
A planar embedded graph $G$ partitions the plane into connected
regions called {\em faces}. Let $F$ denote the set of faces of
$G$. Let $G^* = (F,E^*)$ be the {\em dual graph} of $G$. Its vertex
set is the set $F$ of faces of $G$. There is a one-to-one
correspondence between its edge set $E^*$ and $E$ as follows: for each
edge $e \in E$, there is a corresponding edge $e^* \in E^*$ connecting
the two faces in $G$ that border $e$. Note that $G^*$ may have loops
and multi-edges even when $G$ does not. However, $G^*$ is always a
connected graph, irrespective of whether or not $G$ is. We sometimes
refer to $G$ as the {\em primal graph}. We further denote by $G^{**}$
the graph obtained {from} $G^*$ by deleting self-loops and replacing
multiple edges by a single edge. Let $n$, $m$ and $f$ (respectively
$n^*, m^*, f^*$, and $n^{**}, m^{**}, f^{**}$) denote the number of
vertices, edges and faces in $G$ (respectively $G^*$ and $G^{**}$), and let
$c$ be the number of components in $G$. Then
$e^{**} \le e^* = e $, $f^{**} \le f^* = n-c+1$, and
$n^{**}=n^*=f$. Also, $f \in O(e)$.
Euler's formula states that a planar graph with $c$ components
satisfies $e+c+1=n+f$. Furthermore, if the graph has no self-loops or
multiple edges, it also satisfies $e \le 3n - 6c$.
These definitions generalize naturally if the graph $G$ is embedded on
an orientable surface of higher genus. Throughout this paper, surface
will mean orientable surface. The genus of a graph $G$, denoted
$\gamma(G)$, is the minimum $g$ for which $G$ can be embedded on a
surface $S_g$ of genus $g$. If the graph is connected and has no self-loops
or multiple edges, it satisfies $e \le 3n + 6(\gamma(G)-1)$.
Given an embedding of a graph $G$ on a surface $S_g$, an edge is said
to be a {\em separating edge} if the two faces of the embedding
incident on $e$ are distinct from each other. A cycle $C$ in $G$ is
said to be a {\em separating cycle} if some edge $e$ of $C$ is a
separating edge. In a planar embedding, every cycle is separating,
but this may not be the case for higher genus embeddings.
A combinatorial embedding is a scheme that specifies, for each vertex
$v$, a cyclic permutation of the neighbours of $v$. For connected
graphs, combinatorial embeddings are in one-to-one correspondence with
embeddings on surfaces of appropriately calculated genus.
For a full treatment of this topic, see for instance \cite{Thomassen,White}.
\subsection{The computation model}
Most algorithms in this paper are presented using the concurrent-read
concurrent-write (CRCW) parallel random-access machine PRAM
model, see for instance \cite{JaJa}. To show that a problem is in NC, we describe a
parallel algorithm that, for inputs of size $n$, uses $n^{O(1)}$
processors and runs in $\log^{O(1)} n$ parallel time. These processors
access a global shared memory consisting of $n^{O(1)}$ memory
locations.
For the reduction in \secref{srch-cnt}, we need the notion of oracle
access within NC. For this result alone, we use the equivalent
formulation of NC as problems decided by circuit families $\{C_n
\}_{n>0}$, where $C_n$ is a Boolean circuit with $n^{O(1)}$ {\sc AND},
{\sc OR} and {\sc NOT} gates, depth $\log^{O(1)} n$, and decides
instances of length $n$. Further, given $1^n$ as input, a description
of $C_n$ can be obtained using $\log n$ space. A circuit family
relative to an oracle $B$ (a decision problem) is also allowed to have
query gates, with each such gate having $m$ inputs for some $m\in
n^{O(1)}$. A query gate outputs a 1 if the word formed by the settings
to its input wires is in the oracle language $B$, and outputs 0
otherwise. See, for instance, \cite{vollmertext} for more details.
A problem $A$ is said to
NC-reduce to a decision problem $B$, denoted $A \in \mbox{NC($B$)}$, if
$A$ is decided by an NC circuit family relative to oracle $B$.
\section{Bipartite graphs: Search reduces to counting}
\seclab{srch-cnt}
The main result of this section is that for any subclass of bipartite
graphs closed under deletion, searching for a perfect matching
NC-reduces to counting perfect matchings. Formally,
Let ${\cal F}$ be any class of bipartite
graphs closed under edge deletion. Define the problems
\begin{description}
\item{$\Srch _{{\cal F}}$:} On input $G \in {\cal F}$, output a
perfect matching $M$ in $G$, if one exists.
\item{$\Cnt _{{\cal F}}$:} On input $G \in {\cal F}$, output the
number of perfect matchings in $G$.
\item{$\BCnt _{{\cal F}}$.} This is the decision problem
$$\{\langle G,i,b \rangle \mbox{~the $i$th bit of $\Cnt_{{\cal
F}}(G)$ is $b$~} \}$$
\end{description}
\begin{theorem}
\theolab{reduction} For any class ${\cal F}$ of bipartite graphs
closed under edge deletion, $$\Srch _{{\cal F}} \in \rm{NC}(\BCnt
_{{\cal F}})$$
\end{theorem}
A major tool in proving this result is the technique developed in
\cite{GPST}, where Goldberg {\it et al.} describe a parallel algorithm to
construct a maximum weight matching in a weighted bipartite graph. The
algorithm has two major stages. In the first stage, a feasible
solution (an interior point of \Mp) and a corresponding dual solution
with a small duality gap are obtained. This interior point is in fact
near-optimal; the weight of the feasible solution is less than the
weight of an optimal solution by at most 1/2. In the second stage, the
fractional values of the near-optimal point are carefully rounded to
obtain an optimal integral solution. The first stage needs
$O(\sqrt{m} \log ^2 n\log nC)$ parallel time while the second stage needs
$O(\log n \log nC)$ parallel time, both using polynomially many
processors. Here, $C$ is the maximum absolute value of the weights of
edges in $G$.
We are concerned here with the specialization of the above algorithm
to unweighted bipartite graphs (all edges have weight 1), and with the
problem of perfect matchings. Suppose the given graph $G$, on $2n$
vertices, has a perfect matching. Then we have
\begin{prop}[Section 3 of \cite{GPST}]
\proplab{GPST-1}
Let $G$ be a bipartite graph on $2n$
vertices with at least one perfect matching. An interior point of
\Mp\ with total weight at least $n - 1/2$ can be found in parallel
time $O(\sqrt{m} \log^3 n)$ using polynomially many processors.
\end{prop}
Note that this point is not in the interior of $\PMp = \Fmp$ unless it
is already optimal in the weighted sense.
\begin{prop}[Section 4 of \cite{GPST}]
\proplab{GPST-2}
Let $G$ be a bipartite graph on $2n$
vertices with at least one perfect matching.
From any interior point of
\Mp\ with total weight at least $n - 1/2$, a perfect matching of $G$
can be obtained in NC (parallel time $O(\log^2 n)$).
\end{prop}
Since \propref{GPST-2} already gives an NC bound for navigating from
a near-optimal interior point to a vertex of \Mp, we can hope to obtain an NC
algorithm for finding a perfect matching if the task of
\propref{GPST-1} can also be performed in NC. We observe below that
for a large class of graphs, this is indeed the case. The crucial
observation is the following:
\begin{fact}
\factlab{fmp-opt}
Every interior point of \Fmp\ has
total weight $n$ and is thus optimal in the sense of \cite{GPST}.
\end{fact}
\begin{lemma}
\lemlab{count-implies-interior-pt}
Let ${\cal F}$ be any class of
graphs closed under edge deletion.
For any graph $G \in {\cal F}$, an interior point of
$\PMp \subseteq \Fmp$, if one exists, can be obtained in
NC with oracle access to \BCnt(${\cal F}$).
\end{lemma}
\begin{proof}
For each edge $e \in G$, set $x_e$ to be the ratio of the number of
perfect matchings in which $e$ participates to the total number of
perfect matchings. To compute the values $x_e$, we use the
oracle \BCnt(${\cal F}$) as follows.
\begin{center}
\framebox{
\parbox[t]{6in}{
\begin{tabbing}
Compute $M$ = the number of perfect matchings in $G$. \\
If $M = 0$, then report ``$\PMp = \emptyset$'' and exit. \\
For each \= $e \in E$, pardo: \\
\> Compute $M_e$ = the number of perfect matchings in $G-\{e\}$. \\
\> $x_e = 1 - (M_e/M)$. \\
\> Endif \\
\end{tabbing}
}}
\end{center}
It is clear that this point satisfies \eqnsref{fmp}
and hence is inside \Fmp. It is inside \PMp\ as well, since it
is simply the centroid of all perfect matchings and thus is inside
their convex hull.
\end{proof}
Note that the above result does not even require $G$ to be bipartite.
Using \factref{fmp-opt} and \lemref{count-implies-interior-pt}, we see
that \propref{GPST-1} can be partially tightened as follows:
\begin{prop}
\proplab{GPST-1-impr}
Let ${\cal F}$ be any class of
graphs closed under edge deletion.
For any $G$ in ${\cal F}$,
if \PMp\ is non-empty, then an interior point of
\PMp\ with total weight $n$ can be found in
NC with oracle access to \BCnt(${\cal F}$).
\end{prop}
Since $\Fmp= \PMp \subseteq \Mp$ for bipartite graphs,
putting \propref{GPST-1-impr} and \propref{GPST-2} together
establishes \theoref{reduction}.
For $K_{3,3}$-free graphs, it turns out that \BCnt\ is in NC:
\begin{lemma}[\cite{Vaz}]
\lemlab{cntVaz} The number of perfect matchings in
$K_{3,3}$-free graphs can be computed in NC.
\end{lemma}
\begin{proof}
Given a $K_{3,3}$-free graph $G$, \cite{Vaz} shows how to obtain a
pfaffian orientation of $G$, and \cite{MSV04} shows how to compute the
pfaffian. The absolute value of this pfaffian is the number of perfect
matchings in $G$.
(Note: the absolute value of the pfaffian can also be computed by
computing the square root of the determinant. \cite{MSV04} directly
computes the pfaffian, with its sign, in NC.)
\end{proof}
Hence, using \theoref{reduction}, we can conclude:
\begin{corollary}
There is an NC algorithm that,
given a $K_{3,3}$-free bipartite graph $G$,
finds a perfect matching in $G$ (or reports
that none exists).
\end{corollary}
For regular bipartite graphs, interior points are even easier to
compute. Let $d$ be the degree of every vertex; simply set $x_e = 1/d$
for every edge $e$. Clearly, this assignment satisfies \eqnsref{fmp}.
\begin{prop}
\proplab{regular-implies-interior-pt}
If $G$ is a regular bipartite graph, then an
interior point of $\Fmp\subseteq \Mp$ can be obtained in NC.
\end{prop}
Using \factref{fmp-opt},
\propref{regular-implies-interior-pt}, and \propref{GPST-2},
we have the following corollary.
\begin{corollary}
There is an NC algorithm that,
given a regular bipartite graph $G$,
finds a perfect matching in $G$ (or reports
that none exists).
\end{corollary}
\section{Counting perfect matchings in small genus graphs in NC}
\seclab{torus-count}
In this section we show that the number of perfect matchings in a
graph of genus $g \in O(\log n)$ can be computed in NC.
\subsection{Input and basic operations}
We first describe the {\em polygonal representation} of an oriented
surface $S_g$ of genus $g$. We follow the notation of \cite{GL-EJC1}.
Informally, $S_g$ is a sphere with $g$
handles, and its polygonal representation is obtained by cutting the
$g$ handles of its space model. The polygonal representation consists
of a convex $4g$-gon $B_0$ whose vertices $a_1,\ldots,a_{4g}$ are
numbered clockwise. For $0 \leq i \leq g-1$, the edge $[a_{4i +
1},a_{4i + 2}]$ is identified with
the edge $[a_{4i + 4},a_{4i + 3}]$ via a bridge $B_{1}^i$, and the
edge $[a_{4i + 2}, a_{4i + 3}]$ is identified with the edge
$[a_{4i + 5},a_{4i + 4}]$ via a bridge $B^i_2$. (The vertex $a_{4g+1}$ is, by
convention, the vertex $a_1$.) The bridges $B^i_1$ and $B^i_2$
together constitute the $i$th handle of the sphere. We will
use $[a,b]$ to denote an edge of the convex polygon $B_0$ as opposed to
an edge of the graph. We will refer to two edges of $B_0$ that are
identified as {\em partners}.
Thus a graph $G$ embedded on $S_g$, when translated to the polygonal
representation, has its vertices inside $B_0$. An edge of $G$ might
``cross over'' {from} an edge of $B_0$ to its partner using a bridge.
Our algorithm assumes some combinatorial representation of the
embedding of $G$ within $B_0$ (any scheme for representing planar
graphs suffices), plus some additional information that identifies
points on an edge of $G$ when it crosses over {from} an edge of $B_0$
to its partner. Given such an embedding, we can easily modify existing
NC-algorithms for planar graphs to perform standard operations like
extracting the edges bounding each face of $G$, or constructing the
graph $G^*$ dual to $G$.
For more details concerning embeddings onto non-planar
surfaces, see for instance \cite{Thomassen,White,GL-EJC1}.
\subsection{Counting perfect matchings in P: the Galluccio-Loebl algorithm}
We briefly describe the polynomial time algorithm of Galluccio and
Loebl \cite{GL-EJC1} for counting perfect matchings in $G$.
Galluccio and Loebl actually consider the following generalization of
the counting problem. Let $x_e$ be a distinct variable associated with
each edge $e$ of the graph $G$. The monomial corresponding to a
perfect matching $M$ is $x(M) = \prod_{e \in M} x_e$, the product of
the variables corresponding to edges in $M$. Define $P(G,x)$ to be the
sum of $x(M)$ over of all perfect matchings in the graph; this is
called the {\it generating function of perfect matchings} of $G$. When
all the variables are set to one, $P(G,x)$ evaluates to the number of
perfect matchings in $G$.
\begin{theorem}[Theorem 3.10 of \cite{GL-EJC1}]
\theolab{GLalgo}
Let $G$ be a graph embeddable on an orientable surface of genus $g$.
Then $P(G,x)$ may be expressed as a linear combination of $4^g$
Pfaffians of matrices $A(D)$ where each $D$ is an orientation of $G$.
\end{theorem}
To prove this theorem, the notion of a proper $g$-graph is defined.
\begin{definition}[Definition 2.2 of \cite{GL-EJC1}]
\deflab{g-graph}
A graph $G$ is called a proper $g$-graph
if it may be embedded on $S_g$ satisfying the following conditions:
\begin{enumerate}
\item All vertices are embedded in $B_0$.
\item Each edge uses at most one of the $2g$ bridges.
\item Vertices on the boundary of $B_0$ form a cycle embedded on the
boundary.
\item Endpoints of an edge that uses a bridge are embedded on the
boundary of $B_0$, one vertex on each partner.
\item Each vertex has at most one incident edge not in $G_0$.
\item $G_0$ has a perfect matching $M_0$.
\end{enumerate}
\end{definition}
Also, the proof uses the following convention.
In some situations we want $x_e$ to be hardwired to some number $a_e$
for certain edges $e$. In this case, we instantiate $x_e$ to $a_e$ in the
original polynomial, and we call the resulting polynomial the
generating polynomial for the hardwired graph.
The proof of \theoref{GLalgo} involves three stages:
\begin{enumerate}
\item Obtain from $G$ another graph $G'$ such that $P(G,x)=P(G',x')$
and $G'$ is a proper $g$-graph:
\begin{enumerate}
\item Start with any embedding of $G$ on $S_g$. Without loss of
generality, all vertices can be assumed to be in the interior of $B_0$.
\item If an edge $e$ uses multiple bridges, subdivide it at each point
where it crosses the boundary of $B_0$. This creates an odd-length
path $e_1, \ldots , e_{2k+1}$. This ensures that an edge uses a
bridge at most once (with endpoints on partner edges), and that a
vertex on the boundary of $B_0$ has at most one incident edge that
uses a bridge. Let $x'_{e_1} = x_e$, and $x'_{e_j} =
1$ for $j > 1$.
\item Fix a perfect matching $M$ in $G$. (If none exists, then
$P(G,x)$ is the zero polynomial.) After the above subdivisions, it
yields a perfect matching $M_0$ within $B_0$.
\item Add edges to form a cycle on the boundary of $B_0$. Let $x'_{e} = 0$
for such an edge $e$.
\end{enumerate}
\item Express $P(G',x')$ as a linear combination of $4^g$ terms, each
being the Pfaffian of a matrix $A(D')$, where $D'$ is an orientation
of $G'$. \\
This is established in Theorem 3.8 of \cite{GL-EJC1}. The relevant
orientations $D'$ of $G'$ are obtained as follows: find any basic
Pfaffian orientation $D'_0$ of the (planar) subgraph $G_0$ that is
$G'$ restricted to $B_0$. Also, find Pfaffian orientations $D'_i$ of
each (planar) subgraph $G_i$ that is $G'$ restricted to $B_0$ and
the $i$th bridge, for $i = 1, \ldots ,2g$. Let $-D'_i$ be the
orientation obtained by reversing the orientation $D'_i$. The
relevant orientations of $G'$ are those that equal $D'_0$ in $B_0$,
and for each $i = i,\ldots 2g$, equal either $D'_i$ or $-D'_i$ on the
$i$th bridge (Definitions 2.4, 2.5, 2.6 of \cite{GL-EJC1}). Clearly
there are $2^{2g}$ such orientations $D'$,
each with a signature $r(D') \in \{-1,+1 \}^{2g}$. \\
The coefficient for the Pfaffian of $D'$ in the linear combination is
computed from the signature $r(D')$ by a simple expression; see
Definition 3.4 of \cite{GL-EJC1}.
\item Obtain for each relevant orientation $D'$ of $G'$ an orientation
$D$ of $G$ with the same Pfaffian. \\
To recover an orientation $D$ of $G$, throw away edges with $x'_{e}
= 0$. For an edge $e$ of $G$ that was subdivided into an odd path in
$G'$, orient it in the direction in which an odd number of edges of
the subdivision are oriented in $D'$.
\end{enumerate}
\subsection{Counting perfect matchings}
By modifying the algorithm of Galluccio and Loebl \cite{GL-EJC1}
described above, we obtain a parallel algorithm to count perfect
matchings given a polygonal embedding of the graph $G$. Stage 2 and
Stage 3 above are easily parallelizable. In particular, once the
embedding is available, we can in parallel run $4^g$ algorithms, one
for each possible signature $r(D)$. Each such algorithm computes the
relevant orientation with a given signature, and its Pfaffian. By
using the results from \cite{Vaz} and \cite{MSV04} (as in
\lemref{cntVaz}), each such computation is in NC. Combining the
results into the linear combination is just one more parallel step.
The only non-trivial work we have to do is in stage 1, and even there,
step (c) is the bottleneck; all the other steps are easily seen to be
in NC.
Stage 1 step (c) requires the computation of a perfect matching in the
original graph $G$, which can be done in P. That is, perfect matchings
can be counted provided we have our hands on one such matching.
However, unlike \cite{GL-EJC1}, our ultimate goal is to search for a
perfect matching (counting perfect matchings is a step toward this);
we do not already know how to find one. One way around this would
be as follows: ``Add'' a perfect matching to $G_0$ without violating
planarity of $G_0$. To ensure that the generating function of perfect
matchings does not change as a result, set $x'_{e} = 0$ for these newly
added edges.
However, even such an addition is not exactly trivial. Let $M$ be a
pairing of the vertices of the graph and suppose that $M$ is embedded
within $B_0$ so that the embeddings of any pair of edges in $M$ do not
intersect. Note that an edge $e$ in $M$ may still intersect edges of
$G_0$. However, we may assume that each such intersection is a single
point. Let $e_1, \ldots e_{n/2}$ denote the edges in $M$. We construct
a sequence of graphs $G^0, G^1, \ldots, G^{n/2}$, where $G^0 = G$ and
$G^{i}$ is obtained from $G^{i-1}$ essentially by adding $e_i$ and
introducing vertices at the points where $e_i$ crosses edges in
$G^{i-1}$.
More precisely, suppose that the edge $e_i = (a,b)$ is not an edge of
$G^{i-1}$ and crosses edges $f_j = (u_j, v_j)$ of $G^{i-1}$, for $ 1
\leq j \leq k$, in that order. (If $e_i$ is already an edge in
$G^{i-1}$, we simply set $G^i = G^{i-1}$.) We split each $f_j$ into
three edges $f_{j1}=(u_j,x_j)$, $f_{j2}=(x_j,y_j)$ and
$f_{j3}=(y_j,v_j)$, by adding vertices $x_j$ and $y_j$. We set
$x'_{f_{j1}}=x_{f_j}$, and $x'_{f_{j2}}=x'_{f_{j3}}=1$.
Further, we add the edges $(a,x_1)$, $(y_j,x_{j+1})$ for $1 \leq j
\leq k - 1$, and $(y_k, b)$, and set $x'_e=0$ for these edges.
\figref{crossing} illustrates the setting when the $x_e$ variables
carry specific (fractional) values. Let us call these $0$ weight
edges the {\em edges corresponding to $e_i$}. Note that there is a
monomial-preserving one-to-one correspondence between perfect
matchings in $G^{i-1}$ and perfect matchings in $G^i$ that do not
include any of the $0$ weight edges corresponding to $e_i$. Indeed,
from a perfect matching $N$ in $G^{i-1}$, we obtain the corresponding
perfect matching $N'$ in $G^i$ as follows: if $(u_j,v_j)$ is present
in $N$, we replace it by the edges $(u_j,x_j)$ and $(x_j,v_j)$; if
$(u_j,v_j)$ is not present in $N$, we add the edge $(x_j,y_j)$ to
$N'$. The existence of this correspondence shows that the generating
functions of perfect matchings of $G^{i-1}$ and $G^i$ are the same.
\begin{figure}[ht]
\begin{center}
\epsfxsize=4.5in
\epsfbox{fig-crossing.eps}
\end{center}
\caption{Adding edge $(a,b)$ to transform $G^{i-1}$ to $G^i$.}
\figlab{crossing}
\end{figure}
We conclude that $G^{n/2}$ has the same generating function as $G$.
It also satisfies property 6 of \defref{g-graph} -- indeed the edges
corresponding to edges in $M$ form a perfect matching that lies within
$B_0$. Finally, we note that although our definition of $G^{n/2}$ was
sequential in that we ``add'' edges of $M$ one after another, the
construction can be easily parallelized because the edges of $M$ do
not intersect each other.
The only remaining point to address is obtaining the pairing $M$ in NC. If a
plane drawing of $G$ were available, this would be trivial: sort all
vertices by, say, $x$-coordinate (and break ties by $y$-coordinate),
and pair up vertices in this ordering to obtain a non-crossing
matching. What we actually have, however, is a planar combinatorial
embedding, not a plane embedding, of $G_0$. Using the techniques of
\cite{TV91} (Theorems 5.3 and 5.4), we can retrieve, in NC, a plane
drawing of $G_0$ if $G_0$ is biconnected. If $G_0$ is not biconnected,
we can make it biconnected as follows: identify the cut-vertices of
$G_0$. For each cut-vertex $v$, let its neighbours in cyclic order be
$w_1, w_2, \ldots , w_k$. (If $v$ is on the boundary, then assume that
$w_1$ and $w_k$ are the neighbours on the boundary.) Now introduce
edges forming a path $w_1w_2 \ldots w_k$ that
connects all the neighbours, and set $x'_e=0$ for these edges. This ensures that $v$ is no longer a
cut-vertex, while preserving planarity and the generating function of
matchings.
Thus all stages of the algorithm of \cite{GL-EJC1} can be parallelized,
and we can conclude
\begin{theorem}
\theolab{countingforgenus}
Let $G$ be a graph embedded on $S_g$ given by its polygonal embedding
as above. We can count perfect matchings of $G$ in
parallel time $O(g) + (\log n)^{O(1)}$, using $4^gn^{O(1)}$ processors. In
particular, when $g \in O(\log n)$, the procedure is in NC.
\end{theorem}
Using this in conjunction with \theoref{reduction}, we have
\begin{theorem}
Perfect matchings in bipartite graphs of logarithmic genus, given with
a suitable embedding, can be found in NC. \\
More generally, let $G$ be a bipartite graph embedded on $S_g$ given
by its polygonal embedding as above. We can obtain a perfect matching
of $G$ (or report that none exists) in parallel time $O(g) + (\log
n)^{O(1)}$, using $4^gn^{O(1)}$ processors.
\end{theorem}
\section{A different search technique in small-genus bipartite graphs}
\seclab{our-algo}
In this section, we present a different algorithm for finding a
perfect matching in a logarithmic genus bipartite graph. We first
present the algorithm for planar bipartite graphs, then discuss the
essential points of difference between this and the algorithm of
\secref{srch-cnt}, and then present the extension to small genus
graphs.
We are given an embedding of a planar bipartite graph $G = (V,E)$,
where $V$ is the vertex set and $E$ is the edge set. We assume that
$G$ has no loops or multi-edges.
We assume that the graph $G$ is given to us as an embedding in some standard
form.
\subsection{The Algorithm for planar bipartite graphs}
\subseclab{planar-algo}
The algorithm is shown in \figref{planar-algo}.
We first compute a rational
``flow'' or ``weight''
$x_e \in [0,1]$ on each edge $e \in E$ satisfying the following
{\em conservation constraint}: for each vertex $v \in V$, the {\em demand}
at $v$, defined to be the sum of the weights of edges incident to $v$, equals
one. To do this, we simply set $x_e$ to be the ratio of the number of perfect
matchings in which $e$ participates to the total number of perfect matchings.
It is clear that this assignment satisfies the conservation constraint. As
described in the summary, we can compute this assignment by using the counting
algorithm as a subroutine.
\begin{figure}
\begin{center}
\framebox{
\parbox[t]{6in}{
\begin{tabbing}
Compute $M$ = the number of perfect matchings in $G$. \\
If $M = 0$, exit. \\
For each \= $e \in E$, pardo: \\
\> Compute $M_e$ = the number of perfect matchings in $G-\{e\}$. \\
\> If $M_e = M$ \= Then delete edge $e$ \\
\> \> Else Assign weight $1 - (M_e/M)$ to $(a,b)$. \\
\> Endif \\
while $G$ has a cycle do \\
\> Find a set $S$ of edge-disjoint cycles in $G$. \\
\> For each \= cycle $C \in S$, pardo: \\
\> \> Find the smallest edge weight, say $x$ on edge $e$. \\
\> \> Decrease weight of all edges at even
distance {from} $e$ on $C$ by $x$. \\
\> \> Increase weight of all edges at odd
distance {from} $e$ on $C$ by $x$. \\
\> \> Delete all edges on $C$ whose weight is zero. \\
endwhile
\end{tabbing}
}
}
\end{center}
\caption{Algorithm ${\cal A}$ for finding a perfect matching in a planar
bipartite graph}
\figlab{planar-algo}
\end{figure}
Next, we manipulate the weight on the edges, always maintaining the
conservation constraint, till we obtain an integral assignment of
weights which corresponds to a perfect matching. In what follows, $G$
will always denote the subgraph consisting of the edges with non-zero
weights. When the weight on some edge becomes zero, it is deleted
{from} $G$.
The manipulation of the weights is accomplished by the while loop.
Using the algorithm in \lemref{indcycles}, we pick a
subset of faces in $G$ such that no two faces share an edge. The
number of faces in this subset is a constant fraction of the total
number of faces in $G$. For each face in parallel, we extract a simple
cycle $C$ {from} the edges bounding the face. (Note that such a
simple cycle always exists.) Since $G$ is bipartite, $C$ has an even
number of edges. Let $e$ denote the edge on $C$ with the smallest
weight, and let $x$ denote this weight. We decrease the weights of
all edges of $C$ at an even distance {from} $e$ by $x$, and increase
the weights of all edges of $C$ at an odd distance {from} $e$ by $x$.
(Since $C$ is an even cycle, ``odd distance'' (resp. ``even
distance'') {from} $e$ is well-defined.) We delete {from} $G$ the edge
$e$ and any other edges of $C$ whose weight becomes zero.
In the above step, we can operate on each cycle in parallel
because the cycles are edge-disjoint. It is straightforward to
check that at the end of the step the weight of any edge is in the
range $(0,1]$, and that the conservation constraint continues to
hold. This completes the description of an iteration of the while
loop, and also the algorithm.
The correctness of the algorithm is established below.
\begin{lemma}
\lemlab{correctalgo}
When the algorithm terminates, the edges of $G$ form a perfect matching.
\end{lemma}
\begin{proof}
It is clear that the algorithm terminates with an acyclic graph (i.e.\
forest, since the graph is undirected) $G$ and a weight
$x_e \in (0,1]$ on edge $e$ of $G$ satisfying the conservation constraint.
Let $G'$ be any connected
component of $G$. Due to the conservation constraint, $G'$ is not an isolated
vertex. Since $G$ is acyclic, $G'$ is a tree. Let $v$ be any pendant vertex
of $G'$, and let $(u,v)$ be the unique edge incident on $v$. Because the
demand at $v$ equals one, the weight of $(u,v)$ must equal one. But since the
demand at $u$ does not exceed one, $(u,v)$ is the only edge incident on $u$
as well. Thus, $G'$ consists of just the edge $(u,v)$. It follows that the
edge set of $G$ forms a perfect matching.
\end{proof}
We now show that the procedure is indeed implementable in NC.
\begin{lemma}
\lemlab{indcycles}
In a planar graph $G$ with $f$ faces, a set of $\Omega(f)$
edge-disjoint faces and $\Omega(f)$ edge-disjoint simple
cycles can be found in NC.
\end{lemma}
\begin{proof}
A planar graph $G$ as well as its dual $G^*$ and pruned dual $G^{**}$ are
sparse graphs. So they do not have too many high degree vertices. In
$G^{**}$, call a vertex high-degree if it has 12 or more neighbours. Since
$e^{**} \le 3n^{**}-6 = 3f-6$, there are less than $f/2$ high-degree
vertices; the rest are all of low degree. Now consider the subgraph
of $G^{**}$ induced by these low degree vertices, and construct any maximal
independent set $S$. For each vertex that we put in $S$, at most 11
others stay out. So 1 out of every 12 low-degree vertices must be in
$S$; i.e.\ $S \ge f/24$. And each independent set in $G^{**}$ gives a
set of edge-disjoint of faces in $G$.
To find the set of faces, use any NC algorithm for finding maximal
independent sets in $G^{**}$ (see \cite{Luby} for general graphs, or \cite{He}
for planar graphs). If $G^{**}$ has fewer than 24 faces, use a singleton
set corresponding to any face as the independent set.
For each face $F$ in the above set, consider the graph with
only those edges that bound $F$. A spanning tree in this
graph and a fundamental cycle with respect to it can be
found in NC. And since the faces are edge-disjoint, so are
these cycles.
(If the edges bounding a face do not contain a cycle
(i.e.\ they form a forest), then it must be the case that the entire
graph has only one face.)
\end{proof}
\begin{lemma}
\lemlab{iterlog}
In $O(\log n)$ iterations of the while loop, $G$ becomes acyclic.
\end{lemma}
\begin{proof}
We argue that the number of iterations of the while loop is $\log
|F|$, where $F$ is the initial set of faces. It
follows that the number of iterations is $O(\log n)$.
Since any simple cycle divides the plane into two faces, a one-face
planar graph is acyclic. Thus it suffices to prove that after each
iteration of the while loop, the number of faces in $G$ falls by a
constant fraction. This follows {from} the following two
observations. At the beginning of the loop we pick a subset of
edge-disjoint faces which constitute a constant fraction of the set of
all faces. And at the end of the loop, we delete one edge {from} each
picked face, thus destroying the face.
\end{proof}
\begin{theorem}
\theolab{algoisnc}
Given a planar bipartite graph $G$ on $n$ vertices,
algorithm ${\cal A}$ (from \figref{planar-algo} either produces a
perfect matching $M$ in $G$, or reports that $G$ has no perfect
matching. ${\cal A}$ runs in time $(\log n)^{O(1)}$ using $n^{O(1)}$
processors.
\end{theorem}
\begin{proof}
The
initial assignment of weights satisfying the conservation constraint
can be found in NC (use \lemref{cntVaz}). Each iteration of the
while loop can be implemented in NC. (Use \lemref{indcycles} to find
the set of faces. Killing each face is straightforward.) By
\lemref{iterlog}, the number of iterations of the while loop is
$O(\log n)$.
\end{proof}
\subsection{Comparison with other algorithms}
In the preceding subsection, we described an NC algorithm to construct
a perfect matching in a planar bipartite graph. There are three other
algorithms for this problem: (1) the algorithm of Miller and Naor
\cite{MillerNaor}, (2) the algorithm from \secref{srch-cnt}, where the
part from \propref{GPST-2} is implemented using Gabow's edge
colouring algorithm \cite{Gabow}, and (3) the algorithm from
\secref{srch-cnt}, where the part from \propref{GPST-2} is
implemented using the processor-efficient version of \cite{GPST}.
We comparing our algorithm with each of these.
It has been known for quite some time that computing an $s-t$ max-flow
or min-cut in a planar graph is in NC. All algorithms for these
problems use the correspondence between cuts in the graph and cycles
in the dual graph. This is also true of the Miller-Naor algorithm for
planar bipartite matching, where bipartite matching is viewed as the
problem of computing a flow with multiple sources and sinks. (Note
that the standard reduction of bipartite matching to $s-t$ max-flow
does not maintain planarity.) This correspondence between cuts and
cycles in the dual graph breaks down in graphs of higher genus. We are
not aware of any NC algorithm for max-flow or min-cut in such
graphs. Our algorithm for planar bipartite matching conceptually quite
different {from} the algorithm of Miller and Naor because it does not
use this correspondence, and is thus amenable to higher-genus graphs
as well.
In comparing our algorithm with (2) and (3) above, one notable
difference that is immediately visible is the following: Our algorithm
maintains the invariant that at each stage, we are within the perfect
matching polytope \PMp. This is not true for the algorithms based on
\propref{GPST-2}. These algorithms first round down the
fractional matching $\vec{x}$ to integral multiples of $\alpha =
1/2^{\lceil \log m\rceil +1}$. This process could take one outside
\PMp, since the equality constraint is no longer satisfied at each
vertex unless the initial point already had all edge weights multiples
of $\alpha$. Thus for the perfect matching case, these are not truly
interior-point algorithms.
The crucial observation used in (2), (3) is that though outside \PMp,
the rounded point is within \Mp\ and in fact ``close to'' \PMp. The
algorithm of (2) considers the rounded weights $y_e$, and constructs a
multigraph $G'$ by replacing each edge $e$ with $\Delta y_e$ parallel
edges, where $\Delta = 1/\alpha$. Then $G'$ has maximum degree
$\Delta$, and can be edge-coloured with $\Delta$ colours. The
closeness of $\vec{y}$ to \PMp\ guarantees that at least one colour
class is a perfect matching. This is completely different from
what we do with the interior point.
The algorithm of (3) is closest in spirit to our algorithm. It
manipulates edge weights while monotonically increasing closeness to
\PMp. On the other hand, we manipulate edge weights while maintaining
membership in \PMp, but monotonically decrease the complexity of the
graph itself (\lemref{iterlog}). Also, the algorithm of (3) uses
global weight information (the distribution of weights in an Euler
trail) to decide how to manipulate the weights. Our algorithm uses
global weight-independent information to find a maximal set of
disjoint cycles, but subsequently each cycle is manipulated using
weight information local to the cycle.
\subsection{Extension to small genus graphs}
\subseclab{genus-algo}
Let $G$ be a bipartite graph embedded on an orientable surface $S_g$ of
genus $g$. In this section, we describe how the algorithm of the previous
section can be extended to find a perfect matching in $G$. The overall
scheme is quite similar to the algorithm of \figref{planar-algo}.
\begin{figure}
\framebox{
\parbox[t]{6in}{
\begin{enumerate}
\item Using the counting algorithm as a subroutine, find a convex
combination of perfect matchings of $G$, i.e.\ a weight on each
edge so that the conservation constraint is satisfied at each
vertex of $G$.
\item As long as the graph $G$ has more than one face remaining,
repeat the following. Find a subset of faces in $G$ such that
no two faces share an edge. For
each picked face $f$ in parallel, find a simple separating
cycle $C$ {from}
the edges bounding the face. Manipulate the weight on the edges in
$C$ as before, and delete {from} $G$ the edges with zero weight.
\item The graph $G$ now has only one face, but since it is an embedding
on a surface of higher genus, it might still have cycles. Repeat
the following until the graph becomes acyclic. Pick any
cycle in $G$, and manipulate the weights on the edges of the cycle
until some edge-weight becomes zero. Delete the edges of $C$ with
zero weight {from} the graph.
\end{enumerate}
}}
\caption{Algorithm ${\cal B}$ for finding a perfect matching in a genus $g$
bipartite graph}
\figlab{genus-algo}
\end{figure}
We are left with an acyclic graph with weights satisfying the conservation
constraint. By the argument in \lemref{correctalgo}, this must be a perfect
matching. In the rest of this section, we briefly describe
the NC implementations of each of the above steps when the graph genus
is logarithmically bounded.
In each iteration in Step~2 of the algorithm, we find a subset of
edge-disjoint faces of $G$. A subset whose cardinality is a constant
fraction of the total number of faces of $G$ can be found using the
algorithm of the following lemma.
\begin{lemma}
\lemlab{facesforgenus}
Let $G$ be a graph embedded on $S_g$ given by its polygonal embedding.
We can find a subset of $\Omega(f)$ edge-disjoint faces in $G$ in NC, where
$f$ is the number of faces in $G$, provided $f \ge 4g$.
\end{lemma}
\begin{proof}
We construct the dual $G^*$ of $G$, and delete {from} $G^*$ any
self-loops and multiple copies of any edge to get $G^{**}$. Let
$n^{** }= f$, $e^{**}$, and $f^{**}$ denote, respectively, the number
of vertices, edges, and faces in $G^{**}$. Recall that $G^{**}$ is a
connected graph of genus at most $g$, and $e^{**} \leq 3 n^{**} + 6(g-1)$.
Now, as in \lemref{indcycles}, we can argue that at least $n^{**}/2
-g$ vertices of $G^{**}$ have small (less than 12) degree, and so a
maximal independent set has size at least $n^{**}/24 - g/12$. Since
$n^{**} = f \ge 4g$, this set has size at least $f/48$. And this
independent set
corresponds to a subset of edge-disjoint faces in $G$.
\end{proof}
For each face in the subset, we find an appropriate cycle
bounding part of the
face using the following algorithm.
\begin{lemma}
\lemlab{cyclefromface}
Let graph $G$ be embedded on $S_g$, with more than one face,
and let $f$ be a face of the embedding. There exists a simple
cycle $C$ using edges incident
to $f$ with the following property: every edge of
$C$ is a separating edge. That is,
if we delete any edge in $C$ {from}
$G$, the face $f$ merges with some adjacent face different
{from} $f$. Further, such a cycle can be found in NC.
\end{lemma}
\begin{proof}
We look at the edges incident to $f$ and throw away any edge that has $f$
on both sides of it. It is easy to see that the remaining set of edges
forms a union of simple cycles, and deleting any of these edges causes $f$
to merge with some adjacent face. We pick any one of these cycles.
\end{proof}
\begin{lemma}
\lemlab{genus-iterlog}
In $O(g + \log n)$ iterations of the while loop, $G$ is reduced to a
single face graph.
\end{lemma}
\begin{proof}
The while loop has two phases: first, when there are at least $4g$
faces in the graph, and second, when the reduced graph has fewer than
$4g$ faces.
In the first phase, we select, at the beginning of each
iteration, a subset of edge-disjoint faces which constitute a constant
fraction of the set of all faces. In the second phase, we pick any one face at
the beginning of each iteration.
In either phase, at the end of the loop, we delete one edge {from} each
picked face, such that the picked face then merges with an adjacent
face (that was not picked).
We now argue that the number of iterations of the while loop is
$O(\log |F| + g)$, where $F$ is the initial set of faces.
($|F| \in O(n^2)$.)
After each iteration of the while loop in the first phase, the number
of faces in $G$ falls by a constant fraction; clearly, there are at
most $O(\log |F|)$ such iterations. And the second phase has no more
than $4g$ iterations, since a face is destroyed in each iteration.
\end{proof}
\begin{lemma}
\lemlab{step3}
The number of iterations in Step~3 of the algorithm is at most $2g$.
\end{lemma}
\begin{proof}
The analogue of Jordan's Curve Theorem on the plane states that if a
surface has genus g, then any set of 2g+1 closed curves will make the
surface disconnected. (See for instance \cite{BL}.)
At the beginning of step 3, the graph $G$ is embedded onto $S_g$ and
the embedding has a single face. Since any cycle in $G$ will embed on
to a closed curve on $S_g$, it follows that $G$ has at most $2g$
cycles. And each iteration of step 3 destroys at least one cycle.
\end{proof}
\begin{theorem}
\theolab{genusinNC}
Given a bipartite graph $G$ on $n$ vertices along with its embedding on a
polygonal representation of an oriented surface of genus $g$,
algorithm ${\cal B}$ either produces a perfect
matching $M$ in $G$, or reports that $G$ has no perfect matching.
${\cal B}$ runs in time $(\log n)^{O(1)}g$
using $4^g n^{O(1)}$ processors.
In particular, if $g \in O(\log n)$, then ${\cal B}$ is an NC
algorithm.
\end{theorem}
\begin{proof}
The bounds for step 1 are stated in
\theoref{countingforgenus}. \lemref{facesforgenus} and
\lemref{cyclefromface} show that each iteration of step 2 and of step
3 is in NC. \lemref{genus-iterlog} and \lemref{step3} bound the number
of iterations for steps 2 and 3 respectively.
\end{proof}
\section{Finding a half-integral solution in a small-genus graph in NC}
\seclab{halfint}
In this section we make partial progress towards finding a perfect
matching in a planar graph in NC. Recall that $\PMp \subseteq \Fmp$,
and that once the bipartiteness
condition is relaxed, we no longer have $\PMp = \Fmp$. Our eventual
goal is to find a vertex of \PMp. Here we show that we can find a
vertex of \Fmp\ in NC. Namely, we establish the following theorem.
\begin{theorem}
\theolab{main}
For graphs of logarithmic genus, a vertex of the fractional matching
polytope \Fmp\ (i.e.\ a half-integral solution to the equations
defining \Fmp, with no even cycles) can be found in NC, provided
that the perfect matching polytope \Mp\ is non-empty.
\end{theorem}
As in \secref{our-algo}, we present the
algorithm for the planar case. The extension to small genus is
exactly as in \subsecref{genus-algo}.
Our starting point is the same interior point $p$ computed in the previous
section; namely, the arithmetic mean of all perfect matchings of $G$.
Starting from $p$, we attempt to move towards a vertex.
The basic strategy is to find a large set $S$ of edge-disjoint faces.
Each such face contains a simple cycle, which we try to destroy.
Difficulties arise if the edges bounding the faces in $S$ do not
contain even length simple cycles, since the method of the previous
section works only for even cycles. We describe mechanisms to be used
successively in such cases.
\subsection{Basic Building Blocks}
\subseclab{blocks}
We first describe some basic building blocks, and then describe how to
put them together.
\paragraph{Building block 1:} Simplify, or {\em Standardize}, the graph $G$.
Let $G$ be the current graph, let $x:E\longrightarrow \mathbb{\cal Q}$
be the current assignment of weights to edges, and let $y$ be the
partial assignment finalized so far. The final assignment is
$y:E\longrightarrow \{0,1/2,1 \}$.
\begin{description}
\item[Step 1.1]
For each $e = (u,v) \in E(G)$, if $x_e = 0$, then set $y_e = 0$ and delete
$e$ from $G$.
\item[Step 1.2]
For each $e = (u,v) \in E(G)$, if $x_e = 1$, then set $ y_e = 1$ and
delete $u$ and $v$ from $G$.
(This step ensures that all vertices of $G$ have degree at least 2.)
\item[Step 1.3] Obtain connected components of $G$.
If a component is an odd cycle $C$, then every edge on $C$ must have
weight 1/2. For each $e \in C$, set $y_e = 1/2$. Delete all the
edges and vertices of $C$ from $G$.
If a component is an even cycle $C$, then for some $0 < a < 1$, the
edges on $C$ alternately have weights $a$ and $1-a$. For each $e
\in C$, if $x_e = a $ then set $y_e = 1$ and if $x_e = 1-a$ then set
$y_e=0$. Delete all the edges and vertices of $C$ from $G$.
\item[Step 1.4] Let $V'$ be the set of vertices of degree 2 in $G$.
Consider the subgraph of $G$ induced by $V'$; this is a disjoint
collection of paths. Collapse each such even path to a path of
length 2 and each such odd path to a path of length 1, reassigning
weights as shown in \figref{no-consec-deg-2}. Again, we
stay within the polytope of the new graph, and from any assignment
here, a point in \Fmp\ can be recovered in a straightforward way.
This step ensures that no degree 2 vertex has a degree 2 neighbour.
\begin{figure}[ht]
\begin{center}
\epsfxsize=4.5in
\epsfbox{fig-no-consec-deg-2.eps}
\end{center}
\caption{Transformation assuring that no two consecutive vertices are of degree 2}
\figlab{no-consec-deg-2}
\end{figure}
\item[Step 1.5] For each $v \in V(G)$, if $v$ has degree more than 3,
then introduce some new vertices and edges, rearrange the edges
touching $v$, and assign weights as shown in
\figref{no-high-deg}. This assignment in the new graph is
in the corresponding polytope of the new graph, and from any
assignment here, a point in \Fmp\ can be recovered in a
straightforward way. (This gadget construction was in fact first
used in \cite{DK2}.)
This step ensures that all vertices have degree 2 or 3.
\begin{figure}[ht]
\begin{center}
\epsfxsize=5.5in
\epsfbox{fig-no-high-deg.eps}
\end{center}
\caption{Transformation to remove vertices of degree greater than 3}
\figlab{no-high-deg}
\end{figure}
\end{description}
Note that Steps 1.4 and 1.5 above change the underlying graph. To
recover the point in \Fmp\ from a point in the new graph's polytope,
we can initially allocate one processor per edge. This processor will
keep track of which edge in the modified graph dictates the assignment
to this edge. Whenever any transformation is done on the graph, these
processors update their respective data, so that recovery at the end is
possible.
We will call a graph on which the transformations of building block 1
have been done a {\em standardized graph}.
\paragraph{Building Block 2:} Process an even cycle. This is as in
\secref{our-algo}.
\paragraph{Building Block 3:} Process an odd cycle connected to itself
by a path. Let $C$ be such an odd cycle, with path $P$ connecting $C$
to itself. We first consider the case when $P$ is a single edge,
i.e.\ a chord. The chord $(u,v)$ cuts the cycle into paths
$P_1,P_2$. Let $C_i$ denote the cycle formed by $P_i$ along with the
chord $(u,v)$. Exactly one of $C_1,C_2$ is even; process it as in
Building Block 2.
If instead of a chord, there is some path $P_{u,v}$ connecting $u$ and
$v$ on $C$, the same reasoning holds and so this step can still be
performed.
\paragraph{Building Block 4:} Process a pair of edge-disjoint odd cycles
connected by a path.
Let $C_1$ and $C_2$ be the odd cycles and $P$ the path connecting
them. Note that if $G$ is standardized, then $P$ cannot be of length
$0$. Let $P$ connect to $C_1$ at $u$ and to $C_2$ at $v$. Then the
traversal of $C_1$ beginning at $u$, followed by path $P$ going from
$u$ to $v$, then the traversal of $C_2$ beginning at $v$, followed by
the path $P$ going from $v$ to $u$, is a closed walk of even length.
We make two copies of $P$, one for each direction of traversal. For
edge $e$ on $P$, assign weight $x_e/2$ to each copy. Now treating the
two copies as separate, we have an even cycle which can be processed
according to building Block 2. For each edge $e \in P$, its two copies
are at even distance from each other, so either both increase or both
decrease in weight. It can be seen that after this adjustment, the
weights of the copies still adds up to something between 0 and 1.
This step is illustrated in \figref{even-clow}. The edge on
the path has weight $a$ is split into two copies with weight $a/2$ each.
The dotted edge is the minimum weight edge; thus $w \le a/2$.
\begin{figure}[ht]
\begin{center}
\epsfxsize=4in
\epsfbox{fig-even-clow.eps}
\end{center}
\caption{Manipulating a closed walk of even length}
\figlab{even-clow}
\end{figure}
\subsection{The Algorithm}
\subseclab{halfint-algo}
The idea is to repeatedly identify large sets of edge-disjoint faces,
and then manipulate them, in the process destroying them. The faces
are identified as in \secref{our-algo}, and a simple cycle is
extracted from each face. Even cycles are processed using Building
Block 2. By the building blocks 3 and 4, odd cycles can also be
processed provided we identify paths connecting the cycles to
themselves or other cycles. However, to achieve polylogarithmic time,
we need to process several odd cycles simultaneously, and this
requires that the odd cycles and the connecting paths be
edge-disjoint.
We use the following definition: A path $P$ is said to be a {\em
3-bounded} path if the number of internal vertices of $P$ with
degree 3 is at most $1$. Note that in a standardized graph, a
3-bounded path can have at most 3 internal vertices.
The algorithm can be described as follows:
\begin{enumerate}
\item Find a point $p \in \Mp$ and initialize $x_e$ accordingly.
\item Standardize $G$ (Building block 1; this builds a partial solution
represented in $y$).
\item While $G$ is not empty, repeat the following steps, working in
parallel on each connected component of $G$:
\begin{enumerate}
\item Find a collection $S$ of edge-disjoint faces in $G$, including
at least 1/24 of the faces from each component. Extract a simple
cycle from the edges bounding each face of $S$, to obtain a
collection of simple cycles $T$.
\item Process all even cycles (Building block 2). Remove these
cycles from $T$. Re-standardize.
\item Define each surviving cycle in $T$ to be a cluster. (At later
stages, a cluster will be a set of vertices and the subgraph
induced by this subset.)
While $T$ is non-empty, repeat the following steps:
\begin{enumerate}
\item Construct an auxiliary graph $H$ with clusters as vertices.
$H$ has an edge between clusters $D_1$ and $D_2$ if there is a
3-bounded path between some vertex of $D_1$ and some vertex of
$D_2$ in $G$.
\item Process all clusters having a self-loop in $H$. (Building
Block 3). Remove these clusters from $T$. Re-standardize.
\item Recompute $H$. In $H$, find a maximal matching. Each matched
edge pairs two clusters, between which there is a 3-bounded path
in $G$. In parallel, process all these pairs along with the
connecting path using Building Block 4. Remove the processed
clusters from $T$ and re-standardize.
\item ``Grow'' each cluster: if $D$ is the set of vertices in a
cluster, then first add to $D$ all degree-2 neighbours of $D$,
then add to $D$ all degree-3 neighbours of $D$.
\end{enumerate}
\end{enumerate}
\item Return the edge weights stored in $y$.
\end{enumerate}
\subsection{Correctness}
\subseclab{halfint-correct}
The correctness of the algorithm follows from the following series of
lemmas:
\begin{lemma}
\lemlab{corr-1}
The clusters and 3-bounded paths processed in Step 3(c) are
vertex-disjoint.
\end{lemma}
\begin{proof}
Each iteration of the while loop in Step 3(c) operates on different
parts of $G$. We show that these parts are edge-disjoint, and in
fact even vertex-disjoint. Clearly, this is true when we enter
Step 3(c); the cycles are edge-disjoint by our choice in Step
3(a), and since $G$ has maximum degree 3, no vertex can be on two
edge-disjoint cycles. Changes happen only in steps 3(c)(ii) and
3(c)(iii); we analyze these separately.
Consider Step 3(c)(ii). If two clusters $D_1$ and $D_2$ have
self-loops, then there are 3-bounded paths $\rho_i$ from $D_i$ to
$D_i$, $i = 1,2$. If these paths share a vertex $v$, it can only
be an internal vertex of $\rho_1$ and $\rho_2$, since the clusters
were vertex-disjoint before this step. In particular, $v$ cannot
be a degree-2 vertex. But since $G$ is standardized, deg$(v)$ is
then 3, which does not allow it to participate in two such
paths. So $\rho_1$ and $\rho_2$ must be vertex-disjoint. Thus
processing them in parallel via building block 4 is
valid. Processing clusters with self-loops merely removes them from
$T$; thus the clusters surviving after Step 3(c)(ii) continue to
be vertex-disjoint.
Now consider Step 3(c)(iii). Suppose cluster $D_1$ is matched to
$D_2$ via 3-bounded path $\rho$, $D_3$ to $D_4$ via 3-bounded path
$\eta$. Note that $D_i \neq D_j$ for $i \neq j$, since we are
considering a matching in $H$. Thus, by the same argument as
above, the paths $\rho$ and $\eta$ must be
vertex-disjoint. Thus processing them in parallel via building
block 4 is valid. Processing matched clusters removes them from
$T$; the remaining clusters continue to be vertex-disjoint.
Since Step 3(c)(iii) considers a maximal matching, the clusters
surviving are not only vertex-disjoint but also not connected to each
other by any 3-bounded path.
\end{proof}
\begin{lemma}
\lemlab{corr-2}
Each invocation of the while loop inside Step 3(c) terminates in
finite time.
\end{lemma}
\begin{proof}
To establish this statement, we will show that clusters which
survive Steps 3(c)(ii) and 3(c)(iii) grow appreciably in size. In
particular, they double in each iteration of the while
loop. Clearly, clusters cannot double indefinitely while remaining
vertex-disjoint, so the statement follows. In fact, our proof
establishes that the while loop in Step 3(c) executes $O(\log n)$
times on each invocation.
Let $G$ denote the graph at the beginning of Step 3(c). Consider a
cluster at this point. Let $D_0$ be the set of vertices in the
cluster. Consider the induced subgraph $G[D_0]$ on $D_0$. Notice that
each such $G[D_0]$ contains exactly one cycle, which is an odd cycle
extracted in Step 3(a).
We trace the progress of cluster $D_0$. Let $D_i$ denote the cluster
(or the associated vertex set; we use this notation interchangeably to
mean both) resulting from $D_0$ after $i$ iterations of the while loop
of Step 3(c). If $D_0$ does not survive $i$ iterations, then $D_i$ is
empty.
For any cluster $D$, let 3-size($D$) denote the number of vertices in
$D$ whose degree in $G$ is 3. Let $D'$ denote the vertices of $D$
whose degree in $G$ is 3 but degree in $D$ is 1.
We establish the following claim:
\begin{claim}
For a cluster $D_0$ surviving $i+1$ iterations of the while loop of
Step 3(c), $G[D_i]$ contains exactly one cycle, and furthermore,
\begin{eqnarray*}
|{D_i}'|&\geq&\lfloor 2^{i-1}\rfloor \\
\mbox{3-size}(D_i) &\geq &2^i
\end{eqnarray*}
\end{claim}
\begin{proof_of_claim}
As mentioned earlier, $G[D_0]$ contains exactly one cycle. Thus
3-size($D_0'$) = 0. In fact, each $G[D_j]$, $j \le i$ contains just this
one cycle, because if any other cycle were present in $G[D_j]$, then a
self-loop would be found at the $(j+1)$th stage and the cluster would
have been processed and deleted from $T$ in Step 3(c)(ii); it would
not grow $(i+1)$ times.
It remains to establish the claims on the sizes of $D_i$ and $D_i'$. We
establish these claims explicitly for $i\le 1$, and by induction for $i >
1$.
Consider $i=0$. Clearly, 3-size($D_{0}$) $\geq$ $2^0=1$, and $\lfloor
2^{-1} \rfloor = 0$.
Now consider $i=1$. We know that $D_0$ has gone through two ``Grow''
phases, and that $G[D_1]$ has only one cycle. Notice that each degree 3
vertex in $D_0$ contributes one vertex {\em outside} $D_0$; if its third
non-cycle neighbour were also on the cycle, then the cycle has a chord
detected in Step 3(c)(ii) and $D_0$ does not grow even once. In fact,
since $D_0$ grows twice, the neighbours are not only outside the cycle
but are distinct from each other. Thus for each vertex contributing to
3-size$(D_0)$, one degree-3 vertex is added to $D_1$ and these vertices
are distinct. Thus all these vertices are in $D_1'$ giving $|D_1'| =
\mbox{3-size}(D_0) \ge 1$, and
$\mbox{3-size}(D_1) = \mbox{3-size}(D_0) + |D_1'| \ge 2$.
To complete the induction, assume that the claim holds for $i-1$,
where $i > 1$. In this case, $ \lfloor 2^{i-2}\rfloor = 2^{i-2}$.
Thus 3-size$(D_{i-1}) \ge 2^{i-1}$, and $|D_{i-1}'| \ge 2^{i-2}$.
Each $u \in D_{i-1}'$ has two neighbours, $u_1$ and $u_2$, not in
$D_{i-1}$. These vertices contributed by each member of $D_{i-1}'$
must be disjoint, since otherwise $D_{i-1}$ would have a 3-bounded
path to itself and would be processed at the $i$th stage; it would
not grow the $i$th time. Furthermore, if $u_l$ is of degree 2, let
$u_l'$ denote its degree-3 neighbour other than $u$; otherwise let
$u_l' = u_l$. By the same reasoning, the vertices $u_1',u_2'$
contributed by each $u \in D_{i-1}'$ must also be disjoint. So
$2|D_{i-1}'|$ vertices are added to $D_{i-1}$ in obtaining $D_i$.
All these new vertices must be in $D_i'$ as well, since otherwise
$D_i$ would have a 3-bounded path to itself and would be processed at
the $(i+1)$th stage; it would not grow the $(i+1)$th time.
Hence $|D_i'| = 2|D_{i-1}'| \ge 2 \cdot 2^{i-2} = 2^{i-1}$.
Every degree-3 vertex of $D_{i-1}$ continues to be in $D_i$ and
contributes to 3-size$(D_i)$. Furthermore, all the vertices of $D_i'$
are not in $D_{i-1}$ and also contribute to 3-size$(D_i)$. Thus
$\mbox{3-size}(D_i) = \mbox{3-size}(D_{i-1}) + |D_i'| \ge 2^{i-1} +
2^{i-1} = 2^i$.
\end{proof_of_claim}
Now that the Claim has been proved, its geometric growth implies
\lemref{corr-2}, and in fact implies that
the "while" loop in Step 3(c) executes $O(\log n)$
times in each invocation.
\end{proof}
\begin{lemma}
\lemlab{corr-3}
The while loop of Step 3 terminates in finite time.
\end{lemma}
\begin{proof}
Suppose some iteration of the while loop in Step 3 does not
delete any edge. This means that Step 3(b) does nothing, so $S$
has no even cycles, and Step 3(c) deletes nothing, so the clusters
keep growing. But by the preceding claim, the clusters can grow at
most $O(\log n)$ times; beyond that, either Step 3(c)(ii) or
Step 3(c)(iii) must get executed.
Thus each iteration of the while loop of Step 3 deletes at least one
edge from $G$, so the while loop terminates in finite time.
\end{proof}
\begin{lemma}
\lemlab{corr-4}
After step 2, and after each iteration of the while loop of Step
3, we have a point inside \Fmp.
\end{lemma}
\begin{proof}
It is easy to see that all the building blocks described in
\subsecref{blocks} preserve membership in \Fmp. Hence the
point obtained after Step 2 is clearly inside \Fmp. During Step 3,
various edges are deleted by processing even closed walks. By our
choice of $S$, the even cycles processed simultaneously in Step
3(b) are edge-disjoint. By \lemref{corr-1}, the even closed
walks processed simultaneously in Steps 3(c)(ii) and 3(c)(iii) are
edge-disjoint. Now all the processing involves applying one of the
building blocks, and these blocks preserve membership in \Fmp\
even if applied simultaneously to edge-disjoint even closed
walks. The statement follows.
\end{proof}
\begin{lemma}
\lemlab{corr-5}
When the algorithm terminates, we have a vertex of \Fmp .
\end{lemma}
\begin{proof}
When $G$ is empty, all edges of the original graph have edge
weights in the set $\{0,1/2,1\}$. Consider the graph $H$ induced by
the non-zero edge weights $y_e$. From the description of Building
Block 1, it follows that $H$ is a disjoint union of a partial
matching (with edge weights 1) and odd cycles (with edge weights
1/2). Such a graph must be a vertex of \Fmp\ (see, for instance,
\cite{LP86}).
\end{proof}
\subsection{Analysis}
\subseclab{halfint-analysis}
It is clear that each of the basic steps of the algorithm runs in NC.
The proof of \lemref{corr-2} establishes that the while loop
inside Step 3(c) runs $O(\log n)$ times. To show that the overall
algorithm is in NC, it thus suffices to establish the following:
\begin{lemma}
\lemlab{anal}
The while loop of Step 3 runs $O(\log n)$ times.
\end{lemma}
\begin{proof}
Let $F$ be the maximum number of faces per component of $G$ at the
beginning of step 3. We show that $F$ decreases by a constant fraction
after each iteration of the while loop of step 3. Since $F = O(n)$ for
planar graphs, it will follow that the while loop executes at most
$O(\log n)$ times.
At the start of Step 3, the connected components of $G$ are obtained, and
they are all handled in parallel. Let us concentrate on any one
component. Within each component, unless the component size (and hence
the number of faces $f$ in the embedding of this component) is very small,
$O(1)$, a set of $\Omega(f)$ edge-disjoint faces (in fact, $f/24$
faces) and $\Omega(f)$ edge-disjoint simple cycles can be found in
NC. This is established in Lemma~3 of \cite{MV-STOC00}, which
basically shows that a maximal independent set amongst the low-degree
vertices of the dual is the required set of faces.
So let $T$ be the set of edge-disjoint faces obtained at the beginning
of step 3. If $|T| \le f/24$, then the component is very small, and it
can be processed sequentially in $O(1)$ time. Otherwise, note that
after one iteration of the while loop of Step 3, $T$ is emptied out,
so all the clusters in $T$ get processed. A single processing step
handles either one cluster (cluster with self-loop) or two (clusters
matched in $H$), so at least $|T|/2$ processing steps are executed
(not necessarily sequentially).
Each processing step deletes at least one edge. Let the number of
edges deleted be $k \ge |T|/2$. Of these, $k_1$ are not bridges at the
time when they are deleted and $k_2 = k-k_1$ are bridges when they are
deleted. Each deletion of a non-bridge merges two faces in the
graph. Thus if $k_1 \ge |T|/4$, then at least $|T|/4 \ge f/96$ faces
are deleted; the number of faces decreases by a constant fraction.
If $k_2 > |T|/4$, consider the effect of these deletions. Each bridge
deleted is on a path joining two clusters. Deleting it separates these
two clusters into two different components. Thus after $k_2$ such
deletions, we have at least $k_2$ pairs of separated clusters. Any connected
component in the resulting graph has at most one cluster from each
pair, and hence {\em does not have} at least $k_2$ clusters. Since
each cluster contains an odd cycle and hence a face, the number of
faces in the new component is at most $f - k_2 \le f - |T|/4 \le f -
f/96$. Hence, either way, the new $F$ is at most $95 F / 96$,
establishing the lemma.
\end{proof}
\section{Conclusions}
\seclab{concl}
This paper presents an interior-point method based on counting to
solve the search problem for perfect matchings in NC. The method works
for those subclasses of bipartite graphs for which counting is in NC. A somewhat different and
simpler method works for small genus bipartite graphs. In recent work
\cite{Kul}, our approach has been extended to cubic and polylog degree
bipartite graphs. For these graphs, too, searching for a perfect
matching was already known to be in NC. But the algorithm of
\cite{Kul} is completely different from earlier algorithms and much
closer in spirit to that of \secref{our-algo}. This suggests that the
essence of the algorithm does not hinge on topological constraints
(small genus) but on interior-point manipulations.
The obvious question is how to extend this approach to non-bipartite
graphs. We believe that counting is a harder problem than search;
hence for graphs where counting perfect matchings is in
NC, finding one also ought to be in NC. Our attempt at obtaining this
generalization has worked only partially, and only for small genus
graphs; here we can find a half-integral perfect matching (a vertex of
\Fmp) in NC, provided there is at least one perfect matching to begin
with. Unfortunately, we still do not know any way of navigating from
a vertex of \Fmp\ to a vertex of \PMp\ in general. Proving this at
least for planar graphs would be an important first step.
Note that for planar non-bipartite graphs, a sublinear time
($O(n^{1/2+\epsilon})$) algorithm can be easily devised using
separators: find a separator $S$, match vertices of $S$ sequentially
to some unmatched neighbour, then recursively process the unmatched
components.
Another open problem is to find embeddings of graphs onto surfaces of
small genus in NC, or even to test whether such embeddings exist.
No NC algorithms are known for testing or
embedding onto surfaces of genus greater than 0. While testing whether
a graph has genus at most $k$ is an NP-complete problem
\cite{Thomassen89}, for a fixed $k$ the problem is known to be in P
and even in linear time \cite{Mohar}.
A combinatorially interesting, though not necessarily practical,
question is whether for planar graphs (or for that matter, any class
of graphs where counting perfect matchings is in NC), one can count
half-integral perfect matchings (vertices of \Fmp) in
NC.
\section{Acknowledgements}
We thank Jan Vondr\'ak for pointing us to the reference
\cite{GL-EJC1}. We thank Jaikumar Radhakrishnan for helping us with
the transformation in the proof of \theoref{countingforgenus}. We
thank Srikanth Iyengar and S Venkatesh for helpful discussions. We
thank Laci Babai for suggesting looking at other interior-point method
algorithms in the matching context. We are grateful to the referees,
whose comments helped us to significantly improve the presentation of
our results.
\bibliography{../../master}
\end{document}