Chennai Mathematical Institute, Chennai<EMAIL_ADDRESS>funded
by a grant from Infosys foundation and SERB-MATRICS grant MTR/2017/000480Aalto
University<EMAIL_ADDRESS>by Academy of Finland, Grant
321901Fernuniversität in Hagen<EMAIL_ADDRESS>of
Informatics, University of Warsaw<EMAIL_ADDRESS>by the
ERC CoG grant TUgbOAT no 772346Indian Institute of Technology, Kanpur,
<EMAIL_ADDRESS>of Electronics and IT, India, VVS PhD
programIndian Institute of Technology, Kanpur,
<EMAIL_ADDRESS>Faculty Research Fellowship, Ministry of
Electronics and IT, India Samir Datta, Chetan Gupta, Rahul Jain, Anish
Mukherjee, Vimal Raj Sharma and Raghunath Tewari [100]F.1.3 Complexity
Measures and Classes ReachUL coUL NonZeroCircL NonZeroCircNC L AC^0 TC^0 AC^1
AC^0[⊕] FO(≤,+,×) FO[⊕](≤,+,×) DynAC^0 DynTC^0 DynAC^0[⊕] DynFO DynFO(≤,+,×)
DynFO[⊕] DynFO[⊕](≤,+,×) PM BPM PMDecision BPMDecision PMSearch BPMSearch
MinWtBPMSearch MM BMM BMMDecision BMMSearch MMSize BMMSize MinWtMM MinWtBMM
MinWtBMMSearch Reach Distance Rank John Q. Open and Joan R. Access 2 42nd
Conference on Very Important Topics (CVIT 2016) CVIT 2016 CVIT 2016 December
24–27, 2016 Little Whinging, United Kingdom 42 23

# Reachability and Matching in Single Crossing Minor Free Graphs

Samir Datta  Chetan Gupta  Rahul Jain  Anish Mukherjee  Vimal Raj Sharma
Raghunath Tewari

###### Abstract

We show that for each single crossing graph $H$, a polynomially bounded weight
function for all $H$-minor free graphs $G$ can be constructed in logspace such
that it gives nonzero weights to all the cycles in $G$. This class of graphs
subsumes almost all classes of graphs for which such a weight function is
known to be constructed in logspace. As a consequence, we obtain that for the
class of $H$-minor free graphs where $H$ is a single crossing graph,
reachability can be solved in $\UL$, and bipartite maximum matching can be
solved in $\SPL$, which are small subclasses of the parallel complexity class
$\NC$. In the restrictive case of bipartite graphs, our maximum matching
result improves upon the recent result of Eppstein and Vazirani [16], where
they show an $\NC$ bound for constructing perfect matching in general single
crossing minor free graphs.

###### keywords:

Reachability, Matching, Logspace, Single-crossing minor free graphs

###### category:

##  1 Introduction

Directed graph reachability and perfect matching are two fundamental problems
in computer science. The history of the two problems has been inextricably
linked together from the inception of computer science (and before!) [18]. The
problems and their variants, such as shortest path [13] and maximum matching
[14] have classically been studied in the sequential model of computation.
Since the 1980s, considerable efforts have been spent trying to find parallel
algorithms for matching problems spurred on by the connection to reachability
which is, of course, parallelizable. The effort succeeded only in part with
the discovery of randomized parallel algorithms [22, 27]. While we know that
the reachability problem is complete for the complexity class $\NL$, precise
characterization has proved to be elusive for matching problems. The 1990s saw
attempts in this direction when surprisingly “small” upper bounds were proved
[2] for the perfect matching problem, although in the non-uniform setting. At
roughly the same time, parallel algorithms for various versions of the
matching problem for restricted graph classes like planar [26] and bounded
genus [25] graphs were discovered. The last two decades have seen efforts
towards pinning down the exact parallel complexity of reachability and
matching related problems in restricted graph classes [6, 24, 9, 10, 5, 21,
19, 20]. Most of these papers are based on the method of constructing _nonzero
circulations_.

The circulation of a simple cycle is the sum of its edge-weights in a fixed
orientation (see Section 2 for the definition) and we wish to assign
polynomially bounded weights to the edges of a graph, such that every simple
cycle has a nonzero circulation. Assigning such weights _isolates_ a
reachability witness or a matching witness in the graph [33]. Constructing
polynomially bounded isolating weight function in parallel for general graphs
has been elusive so far. The last five years have seen rapid progress in the
realm of matching problems, starting with [17] which showed that the method of
nonzero circulations could be extended from topologically restricted
(bipartite) graphs to general (bipartite) graphs. A subsequent result extended
this to all graphs [32]. More recently, the endeavour to parallelize planar
perfect matching has borne fruit [30, 4] and has been followed up by further
exciting work [3].

We know that polynomially bounded weight functions that give nonzero
circulation to every cycle can be constructed in logspace for planar graphs,
bounded genus graphs and bounded treewidth graphs [6, 10, 11] . Planar graphs
are both $K_{3,3}$-free and $K_{5}$-free graphs. Such a weight function is
also known to be constructable in logspace for $K_{3,3}$-free graphs and
$K_{5}$-free graphs, individually [5]. A natural question arises if we can
construct such a weight function for $H$-minor-free graphs for any arbitrary
graph $H$. A major hurdle in this direction is the absence of a space-
efficient (Logspace) or parallel algorithm () for finding a structural
decomposition of $H$-minor free graphs. However, such a decomposition is known
when $H$ is a single crossing graph. This induces us to solve the problem for
single crossing minor-free (SCM-free) graphs. An SCM-free graph can be
decomposed into planar and bounded treewidth graphs. Moreover, $K_{3,3}$ and
$K_{5}$ are single crossing graphs. Hence our result can also be seen as a
generalization of the previous results on these classes. There have also been
important follow-up works on parallel algorithms for SCM-free graphs [16].
SCM-free graphs have been studied in several algorithmic works (for example
[31, 7, 12]).

###  1.1 Our Result

In this paper, we show that results for previously studied graph classes
(planar, constant tree-width and $H$-minor free for $H\in\\{K_{3,3},K_{5}\\}$)
can be extended and unified to yield similar results for SCM-free graphs.

######  Theorem 1.1.

There is a logspace algorithm for computing polynomially-bounded, skew-
symmetric nonzero circulation weight function in SCM-free graphs.

An efficient solution to the circulation problem for a class of graphs yields
better complexity bounds for determining reachability in the directed version
of that class and constructing minimum weight maximum-matching in the
bipartite version of that class. Theorem 1.1 with the results of [8, 28],
yields the following:

######  Corollary 1.2.

For SCM-free graphs, reachability is in $\UL\cap\coUL$ and minimum weight
bipartite maximum matching is in $\SPL$.

Also using the result of [35], we obtain that the Shortest path problem in
SCM-free graphs can be solved in $\UL\cap\coUL$.

#### Overview of Our Techniques and Comparison With Previous Results:

We know that for planar graphs and constant treewidth graphs nonzero
circulation weights can be constructed in logspace [6, 11]. We combine these
weight functions using the techniques from Arora et al. [5], Datta et al. [8]
and, Datta et al. [11] together with some modifications to obtain the desired
weight function. In [5], the authors decompose the given input graph $G$
($K_{3,3}$-free or $K_{5}$-free) and obtain a component tree that contains
planar and constant size components. They modify the components of the
component tree so that they satisfy few properties which they use for
constructing nonzero circulation weights (these properties are mentioned at
the beginning of Section 3). The new graph represented by these modified
components preserves the perfect matchings of $G$. Then, they construct a
_working-tree_ of height $O(\log n)$ corresponding to this component tree and
use it to assign nonzero circulation weights to the edges of this new graph.
The value of the weights assigned to the edges of the new graph is exponential
in the height of the working tree.

While $K_{3,3}$-free and $K_{5}$-free graphs can be decomposed into planar and
constant size components, an SCM-free graph can be decomposed into planar and
constant treewidth components. Thus the component tree of the SCM-free graph
would have several non-planar constant treewidth components. While we can
construct a working tree of height $O(\log n)$, this tree would contain
constant-treewidth components and hence make it difficult to find nonzero
circulation weights. A naïve idea would be to replace each constant treewidth
component with its tree decomposition in the working tree. However, the
resultant tree would have the height $O(\log^{2}n)$. Thus the weight function
obtained in this way is of $O(\log^{2}n)$-bit. We circumvent this problem as
follows: we obtain a component tree $T$ of the given SCM-free graph $G$ and
modify its components to satisfy the same property as [5] (however, we use
different gadgets for modification). Now we replace each bounded treewidth
component with its tree decomposition in $T$. Using this new component tree,
say $T^{\prime}$, we define another graph $G^{\prime}$. We use the technique
from [8] to show that if we can construct the nonzero circulation for
$G^{\prime}$, then we can pull back nonzero circulation for $G$. Few points to
note here: (i) pull back technique works because of the new gadget that we use
to modify the components in $T$, (ii) since ultimately we can obtain nonzero
circulation for $G$, it allows us to compute maximum matching in $G$ in
$\SPL$, which is not the case in [5].

###  1.2 Organization of the Paper

After introducing the definitions and preliminaries in Section 2, in Section 3
we discuss the weight function that achieves non-zero circulation in single-
crossing minor free graphs and its application to maximum matching in Section
4. Finally, we conclude with Section 5.

##  2 Preliminaries and Notations

#### Tree decomposition:

Tree decomposition is a well-studied concept in graph theory. Tree
decomposition of a graph, in some sense, reveals the information of how much
tree-like the graph is. We use the following definition of tree decomposition.

######  Definition 2.1.

Let $G(V,E)$ be a graph and $\tilde{T}$ be a tree, where nodes of the
$\tilde{T}$ are $\\{B_{1},\ldots,B_{k}\mid B_{i}\subseteq V\\}$ (called bags).
$T$ is called a tree decomposition of $G$ if the following three properties
are satisfied:

  * •

$B_{1}\cup\ldots\cup B_{k}=V$,

  * •

for every edge $(u,v)\in E$, there exists a bag $B_{i}$ which contains both
the vertices $u$ and $v$,

  * •

for a vertex $v\in V$, the bags which contain the vertex $v$ form a connected
component in $\tilde{T}$.

The width of a tree decomposition is defined as one less than the size of the
largest bag. The treewidth of a graph $G$ is the minimum width among all
possible tree decompositions of $G$. Given a constant treewidth graph $G$, we
can find its tree decomposition $\tilde{T}$ in logspace such that $\tilde{T}$
has a constant width [15].

######  Lemma 2.2 ([15]).

For every constant $c$, there is a logspace algorithm that takes a graph as
input and outputs its tree decomposition of treewidth at most $c$, if such a
decomposition exists.

######  Definition 2.3.

Let $G_{1}$ and $G_{2}$ be two graphs containing cliques of equal size. Then
the _clique-sum_ of $G_{1}$ and $G_{2}$ is formed from their disjoint union by
identifying pairs of vertices in these two cliques to form a single shared
clique, and then possibly deleting some of the clique edges.

For a constant $k$, a $k$-clique-sum is a clique-sum in which both cliques
have at most $k$ vertices. One may also form clique-sums of more than two
graphs by repeated application of the two-graph clique-sum operation. For a
constant $W$, we use the notation $\langle\mathcal{G}_{P,W}\rangle_{k}$ to
denote the class of graphs that can be obtained by taking repetitive
$k$-clique-sum of planar graphs and graphs of treewidth at most $W$. In this
paper, we construct a polynomially bounded skew-symmetric weight function that
gives nonzero circulation to all the cycles in a graph
$G\in\langle\mathcal{G}_{P,W}\rangle_{3}$. Note that if a weight function
gives nonzero circulations to all the cycles in the biconnected components of
$G$, it will give nonzero circulation to all the cycles in $G$ because no
simple cycle can be a part of two different biconnected components of $G$. We
can find all the biconnected components of $G$ in logspace by finding all the
articulation points. Therefore, without loss of generality, assume that $G$ is
biconnected.

The _crossing number_ of a graph $G$ is the lowest number of edge crossings of
a plane drawing of $G$. A _single-crossing_ graph is a graph whose crossing
number is at most 1. SCM-free graphs are graphs that do not contain $H$ as a
minor, where $H$ is a fixed single crossing graph. Robertson and Seymour have
given the following characterization of SCM-free graphs.

######  Theorem 2.4 ([29]).

For any single-crossing graph $H$, there is an integer $c_{H}\geq 4$
(depending only on $H$) such that every graph with no minor isomorphic to $H$
can be obtained as $3$-clique-sum of planar graphs and graphs of treewidth at
most $c_{H}$.

#### Component Tree:

In order to construct the desired weight function for a graph
$G\in\langle\mathcal{G}_{P,W}\rangle_{3}$, we decompose $G$ into smaller
graphs and obtain a component tree of $G$ defined as follows: we first find
$3$-connected and $4$-connected components of $G$ such that each of these
components is either planar or of constant treewidth. We know that these
components can be obtained in logspace [34]. Since $G$ can be formed by taking
repetitive $3$-clique-sum of these components, the set of vertices involved in
a clique-sum is called a separating set. Using these components and separating
sets, we define a component tree of $G$. A component tree $T$ of $G$ is a tree
such that each node of $T$ contains a $3$-connected or $4$-connected component
of $G$, i.e., each node contains either a planar or constant treewidth
subgraph of $G$. There is an edge between two nodes of $T$ if the
corresponding components are involved in a clique-sum operation. If two nodes
are involved in a clique-sum operation, then copies of all the vertices of the
clique are present in both components. It is easy to see that $T$ will always
be a tree. Within a component, there are two types of edges present, real and
virtual edges. Real edges are those edges that are present in $G$. Let
$\\{a,b,c\\}$(or $\\{a,b\\}$) be a separating triplet(or pair) shared by two
nodes of $T$, then there is a clique $\\{a,b,c\\}$ (or $\\{a,b\\}$) of virtual
edges present in both the components. Suppose there is an edge present in $G$
between any pair of vertices of a separating set. In that case, there is a
real edge present between that pair of vertices parallel to the virtual edge,
in exactly one of the components which share that separating set.

#### Weight function and circulation:

Let $G(V,E)$ be an undirected graph with vertex set $V$ and edge set $E$. By
$\stackon[-4.2pt]{E}{\,\smash{\stackon[-1.95pt]{\mathchar
382\relax}{\rotatebox{180.0}{$\mathchar 382\relax$}}}}$, we denote the set of
bidirected edges corresponding to $E$. Similarly, by
$G(V,\stackon[-4.2pt]{E}{\,\smash{\stackon[-1.95pt]{\mathchar
382\relax}{\rotatebox{180.0}{$\mathchar 382\relax$}}}})$, we denote the graph
corresponding to $G(V,E)$ where each of its edges is replaced by a
corresponding bidirected edge. A weight function
$w:\stackon[-4.2pt]{E}{\,\smash{\stackon[-1.95pt]{\mathchar
382\relax}{\rotatebox{180.0}{$\mathchar 382\relax$}}}}\rightarrow\mathbb{Z}$
is called skew-symmetric if for all
$e\in\stackon[-4.2pt]{E}{\,\smash{\stackon[-1.95pt]{\mathchar
382\relax}{\rotatebox{180.0}{$\mathchar 382\relax$}}}}$, $w(e)=-w(e^{r})$
(where $e^{r}$ represent the edge with its direction reversed). We know that
if $w$ gives nonzero circulation to every cycle that consists of edges of
$\stackon[-4.2pt]{E}{\,\smash{\stackon[-1.95pt]{\mathchar
382\relax}{\rotatebox{180.0}{$\mathchar 382\relax$}}}}$ then it isolates a
directed path between each pair of vertices in
$G(V,\stackon[-4.2pt]{E}{\,\smash{\stackon[-1.95pt]{\mathchar
382\relax}{\rotatebox{180.0}{$\mathchar 382\relax$}}}})$. Also, if $G$ is a
bipartite graph, then the weight function $w$ can be used to construct a
weight function $w^{\textrm{{\tiny{und}}}}:E\rightarrow\mathbb{Z}$ that
isolates a perfect matching in $G$ [33].

A convention is to represent by $\left<w_{1},\ldots,w_{k}\right>$ the weight
function that on edge $e$ takes the weight $\sum_{i=1}^{k}{w_{i}(e)B^{k-i}}$
where $w_{1},\ldots,w_{k}$ are weight functions such that
$\max_{i=1}^{k}{(nw_{i}(e))}\leq B$.

#### Complexity Classes:

The complexity classes and are the classes of languages accepted by
deterministic and non-deterministic logspace Turing machines, respectively.
$\UL$ is a class of languages that can be accepted by an $\NL$ machine that
has at most one accepting path on each input, and hence $\UL\subseteq\NL$.
$\SPL$ is the class of languages whose characteristic function can be written
as a logspace computable integer determinant.

##  3 Weight function

In order to construct the desired weight function for a given graph
$G_{0}\in\langle\mathcal{G}_{P,W}\rangle_{3}$, we modify the component tree
$T_{0}$ of $G_{0}$ such that it has the following properties.

  * •

No two separating sets share a common vertex.

  * •

A separating set is shared by at most two components.

  * •

any virtual triangle, i.e., the triangle consists of virtual edge, in a planar
component is always a face.

Let $T$ be this modified component tree, and $G$ be the graph represented by
$T$. We show that if we have a weight function that gives nonzero circulation
to every cycle in $G$, then we can obtain a weight function that will give
nonzero circulation to all the cycles in $G_{0}$. Arora et al. [5] showed how
a component tree satisfying these properties can be obtained for
$K_{3,3}$-free and $K_{5}$-free graphs. We give a similar construction below
and show that we can modify the components of $T_{0}$ such that $T$ satisfies
the above properties (see Section 3.1). Note that if the graphs inside two
nodes of $T_{0}$ share a separating set $\tau$ and they both are constant
tree-width graphs, then we can take the clique-sum of these two graphs on the
vertices of $\tau$, and the resulting graph will also be a constant tree-width
graph. Therefore, we can assume that if two components share a separating set,
then either both of them are planar, or one of them is planar and the other is
of constant tree-width.

###  3.1 Modifying the Component Tree

In this section, we show that how we obtain the component tree $T$ from
$T_{0}$ so that it satisfies the above three properties.

#### (i) No two separating sets share a common vertex:

For a node $D$ in $T_{0}$, let $G_{D}$ be the graph inside node $D$. Assume
that $G_{D}$ contains a vertex $v$ which is shared by separating sets
$\tau_{1},\tau_{2},\ldots,\tau_{k}$, where $k>1$, present in $G_{D}$. We
replace the vertex $v$ with a gadget $\gamma$ defined as follows: $\gamma$ is
a star graph such that $v$ is the center node and $v_{1},,v_{2},\ldots,v_{k}$
are the leaf nodes of $\gamma$. The edges which were incident on $v$ and had
their other endpoints in $\tau_{i}$, will now incident on $v_{i}$ for all
$i\in[k]$. All the other edges which were incident on $v$ will continue to be
incident on $v$. We do this for each vertex which is shared by more than one
separating set in $G_{D}$. Let $G_{D^{\prime}}$ be the graph obtained after
replacing each such vertex with gadget $\gamma$. It is easy to see that if
$G_{D}$ was a planar component, then $G_{D^{\prime}}$ will also be a planar
component. We show that the same holds for constant tree-width components as
well.

Figure 1: (Left)A separating set $\\{x_{1},x_{2}\\}$ is shared by components
$D_{1},D_{2}$ and $D_{3}$. (Right) Replace them by adding the gadget $\beta$
and connect $D_{1},D_{2}$ and $D_{3}$ to $\beta$.

######  Claim 1.

If $G_{D}$ is a constant treewidth graph, then $G_{D^{\prime}}$ will also be
of constant treewidth.

######  Proof 3.1.

Let $T_{D}$ be a tree decomposition of $G_{D}$ such that each bag of $T_{D}$
is of constant size, i.e., contains some constant number of vertices. Let $v$
be a vertex shared by $k$ separating sets $\\{x_{i},y_{i},v\\}$, for all
$i\in[k]$ in $G_{D}$. Let $B_{1},B_{2},\ldots B_{k}$ be the bags in $T_{D}$
that contain separating sets
$\\{x_{1},y_{1},v\\},\\{x_{2},y_{2},v\\},\ldots,\\{x_{k},y_{k},v\\}$
respectively (note that one bag may contain many separating sets). Now we
obtain a tree decomposition $T_{D^{\prime}}$ of the graph $G_{D^{\prime}}$
using $T_{D}$ as follows: add the vertices $v_{i}$ in the bag $B_{i}$, for all
$i\in[k]$. Repeat this for each vertex $v$ in $G_{D}$, which is shared by more
than one separating set to obtain $T_{D^{\prime}}$. Note that in each bag of
$T_{D}$ we add at most one new vertex with respect to each separating set
contained in the bag in order to obtain $T_{D^{\prime}}$. Since each bag in
$T_{D}$ can contain vertices of only constant many separating sets, size of
each bag remain constant in $T_{D^{\prime}}$. Also, $T_{D^{\prime}}$ is a tree
decomposition of $G_{D^{\prime}}$.

#### (ii) A separating set is shared by at most two components:

Assume that a separating set of size $t$, $\tau=\\{x_{i}\\}_{i\leq t}$ is
shared by $k$ components $D_{1},D_{2},\ldots D_{k}$, for $k>2$, in $T_{0}$.
Let $\beta$ be a gadget defined as follows: the gadget consists of $t$ star
graphs $\\{\gamma_{i}\\}_{i\leq t}$ such that $x_{i}$ is the center node of
$\gamma_{i}$ and each $\gamma_{i}$ has $k$ leaf nodes
$\\{x_{i}^{1},x_{i}^{2},\ldots x_{i}^{k}\\}$. There are virtual cliques
present among the vertices $\\{x_{i}^{j}\\}_{i\leq t}$ for all $j\in[k]$ and
among $\\{x_{i}\\}_{i\leq t}$ (see Figure 1). If there is an edge present
between any pair of vertices in the set $\\{x_{i}\\}_{i\leq t}$ in the
original graph, then we add a real edge between respective vertices in
$\beta$. $\beta$ shares the separating set $\\{x_{i}^{j}\\}_{i\leq t}$ with
the component $D_{j}$ for all $j\in[k]$.

Note that in this construction, we create new components ($\beta$) while all
the other components in the component tree remain unchanged. Notice that the
tree-width of $\beta$ is constant (at most $5$ to be precise). We can define a
tree decomposition of $\beta$ of tree-width $5$ as follows:
$B_{0},B_{1}^{\prime},B_{2}^{\prime},\ldots,B_{k}^{\prime}$ be the bags in the
tree decomposition such that $B_{0}=\\{x_{1},x_{2},x_{3}\\}$,
$B_{i}^{\prime}=\\{x_{1},x_{2},x_{3},x^{i}_{1},x^{i}_{2},x^{i}_{3}\\}$ and
there is an edge from $B_{0}$ to $B_{i}^{\prime}$ for all $i\in[k]$.

#### (iii) Any virtual triangle, i.e., the triangle consists of virtual edges,
in a planar component is always a face:

$3$-cliques in a $3$-clique sum of a planar and a bounded tree-width component
is always a face in the planar component. This is because suppose there is a
planar component $G_{i}$ in which the $3$-clique on $u,v,w$ occurs but does
not form a face. Then the triangle $u,v,w$ is a separating set in $G_{i}$,
which separates the vertices in its interior $V_{1}$ from the vertices in its
exterior $V_{2}$. Notice that neither of $V_{1},V_{2}$ is empty by assumption
since $u,v,w$ is not a face. However, then we can decompose $G_{i}$ further.

###  3.2 Preserving nonzero circulation:

We can show that if we replace a vertex with the gadget $\gamma$, then the
nonzero-circulation in the graph remains preserved: let $G_{1}(V_{1},E_{1})$
be a graph such that a vertex $v$ in $G_{1}$ is replaced with the gadget
$\gamma$ (star graph). Let this new graph be $G_{2}(V_{2},E_{2})$. We show
that if we have a skew-symmetric weight function $w_{2}$ that gives nonzero
circulation to every cycle in
$G_{2}(V_{2},\stackon[-4.2pt]{E}{\,\smash{\stackon[-1.95pt]{\mathchar
382\relax}{\rotatebox{180.0}{$\mathchar 382\relax$}}}}_{2})$, then we can
obtain a skew-symmetric weight function $w_{1}$ that gives nonzero circulation
to every cycle in
$G_{1}(V_{1},\stackon[-4.2pt]{E}{\,\smash{\stackon[-1.95pt]{\mathchar
382\relax}{\rotatebox{180.0}{$\mathchar 382\relax$}}}}_{2})$ as follow. Let
$u_{1},u_{2},\ldots,u_{k}$ be the neighbors of $v$ in $G_{1}$. For the sake of
simplicity, assume that $v$ is replaced with $\gamma$ such that $\gamma$ has
only two leaves $v_{1}$ and $v_{2}$ and $v$ is the center of $\gamma$. Now
assume that $u_{1},u_{2},\ldots,u_{j}$ become neighbors of $v_{1}$ and,
$u_{j+1},u_{j+2},\ldots,u_{k}$ become neighbors of $v_{2}$ in $G_{2}$, for
some $j<k$. We define a function $P$ that maps each edge of $G_{1}$ to at most
two edges of $G_{2}$ as follows. For edge $(u_{i},v)$ in $G_{1}$,

$P(u_{i},v)=\begin{cases}\\{(u_{i},v_{1}),(v_{1},v)\\},&\text{ if $u_{i}$ is a
neighbor of $v_{1}$ in $G_{2}$, }\\\ \\{(u_{i},v_{2}),(v_{2},v)\\},&\text{ if
$u_{i}$ is a neighbor of $v_{2}$ in $G_{2}$. }\end{cases}$

For all the other edges $e$ of $G_{1}$, $P(e)=\\{e\in G_{2}\\}$. Now given
weight function $w_{2}$ for $G_{2}$, we define weight function $w_{1}$ for
$G_{1}$ as follows:

$\displaystyle w_{1}(e)=\sum_{e^{\prime}\in P(e)}w_{2}(e^{\prime})$

For any
${F}\subseteq\stackon[-4.2pt]{E_{1}}{\,\smash{\stackon[-1.95pt]{\mathchar
382\relax}{\rotatebox{180.0}{$\mathchar 382\relax$}}}}$, we define
$P({F})=(P(e)\mid e\in{F})$. Let $C$ be a simple cycle in $G_{1}$. Notice that
the set of edges in $P(C)$ form a walk in $G_{2}$. Also, note that for some
edges $e$ of $G_{2}$ both $e$ and $e^{r}$ may appear in $P(C)$. Let
$\hat{E}_{2}(C)$ be the set of edges in $P(C)$ such that for each
$e\in\hat{E}_{2}(C)$, both $e$ and $e^{r}$ appear in $P(C)$. Since our weight
function is skew-symmetric, we know that
$\sum_{e\in\hat{E}_{2}(C)}w_{2}(e)=0$. Also, notice that set of edges in the
set $P(C)-\hat{E}_{2}(C)$ form a simple cycle in $G_{2}$ (proof of this is
same as the proof of Claim 3, that we prove later in this paper). Let
$C^{\prime}$ be the simple cycle in $G_{2}$ formed by the edges in the set
$P(C)-\hat{E}_{2}(C)$. We know that, $\sum_{e\in C}w_{1}(e)=\sum_{e\in
P(C)}w_{2}(e)=\sum_{e\in
C^{\prime}}w_{2}(e)+\sum_{e\in\hat{E}_{2}(C)}w_{2}(e)$ and since
$\sum_{e\in\hat{E}_{2}(C)}w_{2}(e)=0$ we have, $\sum_{e\in
C}w_{1}(e)=\sum_{e\in C^{\prime}}w_{2}(e).$

Therefore, we can say that if $w_{2}$ gives nonzero circulation to
$C^{\prime}$, then $w_{1}$ gives nonzero circulation to $C$. To satisfy
property $1$ on the component tree, we replace vertices of the graph with
$\gamma$. Furthermore, to satisfy property $2$, we replace vertices with the
gadget $\beta$, which contains nothing but multiple copies of $\gamma$. Thus
from above, we can conclude that these constructions preserve the nonzero
circulation. Now we will work with the graph $G$ and the component tree $T$.

###  3.3 Tree decomposition

Note that the component tree $T$ of $G$ is also a tree decomposition of $G$ in
the sense that we can consider the nodes of the component tree as bags of
vertices. We know that $T$ contains two types of nodes: (i) nodes that contain
planar graphs, (ii) nodes that contain constant tree-width graphs. We call
them p-type and c-type nodes, respectively.

Now we will construct another tree decomposition $T^{\prime}$ of $G$ using the
component tree $T$. $T^{\prime}$ have two types of bags: (i) A bag with
respect to each p-type node of $T$, which contains the same set of vertices as
the p-type node, and (ii) bags obtained from tree decomposition of the
component inside each c-type node. For a node $N$ of $T$, let $G_{N}$ denote
the graph inside node $N$. Let $V(G_{N})$ denote the vertices in the graph
$G_{N}$ and $T_{N}$ be a tree decomposition of $G_{N}$ obtained using Lemma
2.2.

  * •

Bags of $T^{\prime}$ are defined as follows: $\\{V({G_{N}})\mid N\in T,\text{
where $N$ is a {p-type }node in $T$}\\}\;\bigcup\;\\{B\mid B\in T_{N},\text{
where $N$ is a {c-type }node in $T$}\\}$. We know that in a tree decomposition
of a graph $H$, for each clique in $H$, there exists a bag in the tree
decomposition of $H$ that contains all the vertices of the clique. Let $\tau$
be a separating set present in the graph contained in a c-type node $N$ of
$T$. While constructing a tree decomposition $T_{N}$, we consider the virtual
clique present among the vertices of $\tau$ as a part of $G_{N}$. This ensures
that there exists a bag in $T_{N}$ that contains all the vertices of $\tau$.

  * •

Edges in $T^{\prime}$ are defined as follows: (i) for a c-type  node $N$, let
$B$ and $B^{\prime}$ be two bags in $T_{N}$. If an edge in $T_{N}$ connects
$B$ and $B^{\prime}$, then add an edge between them in $T^{\prime}$ as
well,(ii) let $N^{\prime}$ and $N^{\prime\prime}$ be two adjacent nodes in $T$
such that they share a separating set $\tau$. As mentioned above, we know that
either both $N^{\prime}$ and $N^{\prime\prime}$ are p-type or one of them is
p-type and the other one is a c-type node. If both of them are p-type : we add
an edge between the bags in $T^{\prime}$ that contain the vertices
$V(G_{N^{\prime}})$ and $V(G_{N^{\prime\prime}})$. If $N^{\prime}$ is a p-type
and $N^{\prime\prime}$ is a c-type node: remember that we replaced node
$N^{\prime\prime}$ by its tree decomposition. let $B$ be any bag in
$T_{N^{\prime\prime}}$ which contains all the vertices of $\tau$. We add an
edge between the bag containing vertices $V(G_{N})$ and $B$.

It is easy to see that $T^{\prime}$ is also a tree decomposition of $G$. From
Lemma 2.2, we can say that the overall construction of $T^{\prime}$ remains in
logspace. For simplicity, we rename the bags of $T^{\prime}$ to
$B_{1},B_{2},\ldots,B_{k}$. Let $B_{i}$ be a bag in $T^{\prime}$ corresponding
to a node $N$ in $T$. If $N$ contains a separating set $\tau$, then the set of
vertices of $\tau$ is also called a separating set in $B_{i}$. We will need
this notion later on while constructing the weight function.

Note that Arora et al. [5] obtained a component tree $\hat{T}$ of an input
graph $\hat{G}$ such that each node of $\hat{T}$ contains either a planar
graph or a constant size graph. Then they show that for a cycle $C$ in
$\hat{G}$, the nodes which contain edges of $C$ form a connected component of
$\hat{T}$. They use this property to construct the desired weight function.
Here we can say that $T^{\prime}$ is also a component tree of $G$ such that
each node of $T^{\prime}$ contains a planar graph or a constant size graph, in
a sense that we assign each edge $e$ of $G$ to one of the bags of
$T^{\prime}$, which contains both the endpoints of $e$. However, we cannot
claim that for a cycle $C$, the bags containing edges of $C$ form a connected
component in $T^{\prime}$ (for example, see Figure 2). Thus in this paper, we
use the tree decomposition $T^{\prime}$ to construct another graph
$G^{\prime}$ and associate edges of $G^{\prime}$ to the bags to $T^{\prime}$
such that for each cycle $C^{\prime}$ in $G^{\prime}$, the bags which have
edges of $C^{\prime}$ associated with them, form a connected component in
$T^{\prime}$. We show that if we can construct a skew-symmetric weight
function for $G^{\prime}$ such that it gives nonzero circulation to every
cycle in $G^{\prime}$, then we can obtain a skew-symmetric weight function for
$G$, which gives nonzero circulations to all the cycles in $G$.

Figure 2: Assume $C$ (left) is a constant treewidth component of $G$. We
replace $C$ with its tree decomposition (right) in the component tree
$T^{\prime}$ and associated each edge of $C$ with one of the bags in the tree
decomposition, as shown in the figure. Notice that for cycle abfghedca the
bags ($B_{1},B_{2},B_{5}$ and $B_{6}$), which have edges of the cycle
associated with them, do not form a connected component.

###  3.4 Construction of G’

We construct $G^{\prime}(V^{\prime},E^{\prime})$ from the tree decomposition
$T^{\prime}$ of $G(V,E)$ as follows. We borrow notation from Datta et al.
[11]. Without loss of generality, assume that $T^{\prime}$ is a rooted tree
and the parent-child relationship is well defined.

  * •

Vertex set $V^{\prime}=\\{v_{B_{i}}\mid B_{i}\in T^{\prime},v\in B_{i}\\}$,
i.e., for each vertex $v$ of the $G$, we have copies of $v$ in $G^{\prime}$
for each bag $B_{i}$ of $T^{\prime}$ in which $v$ appears. Copies of vertices
of a separating set are also called a separating set in $G^{\prime}$.

  * •

Edge set $E^{\prime}=\\{(u_{B_{i}},v_{B_{i}})\mid(u,v)\in E,\;u\notin
parent(B_{i})\;or\;v\notin
parent(B_{i})\\}\;\bigcup\;\\{(v_{B_{i}},v_{B_{j}})\mid\text{$B_{i}$ and
$B_{j}$ are adjacent in $T^{\prime}$}\\}$. In other words, we add an edge
between the two vertices $u$ and $v$ of same bag $B_{i}$ if there is an edge
between those vertices in $G$ and no ancestor of $B_{i}$ in $T^{\prime}$
contains both the vertices $u$ and $v$. We add an edge between two copies of a
vertex if the bags they belong to, are adjacent in $T^{\prime}$.

######  Lemma 3.2.

Given a polynomially bounded, skew-symmetric weight function $w^{\prime}$ that
gives a nonzero circulation to every cycle in $G^{\prime}$, we can find a
polynomially bounded, skew-symmetric weight function $w$ for $G$ that gives a
nonzero circulation to every cycle in $G$.

Proof of Lemma 3.2 is given in the Appendix. Now the only thing remaining is
the logspace construction of the polynomially bounded skew-symmetric weight
function $w^{\prime}$.

### Constructing Weight Function for G’

To construct the weight function $w^{\prime}$ for $G^{\prime}$, we associate
each edge of $G^{\prime}$ with some bag of $T^{\prime}$. Let
$(u_{B_{i}},v_{B_{j}})$ be an edge in $G^{\prime}$: (i) if $i=j$, i.e., if
$B_{i}$ and $B_{j}$ are the same bags. In this case associated
$(u_{B_{i}},v_{B_{j}})$ with that bag, (ii) if $i\neq j$: by our construction
of $G^{\prime}$ we know that either $B_{i}$ is the parent of $B_{j}$ or
$B_{j}$ is the parent of $B_{i}$ (i.e. $u_{B_{i}}$ and $v_{B_{j}}$ are the
copies of a same vertex of $G$). In both the cases, associate
$(u_{B_{i}},v_{B_{j}})$ with the parent bag. We will use the following claim
later in the paper.

######  Claim 2.

For any cycle, $C$ in $G^{\prime}$, the bags of $T^{\prime}$ which have some
edge of $C$ associated with them, form a connected component in $T^{\prime}$.

The weight function $w^{\prime}$ is similar to the one constructed for
$K_{3,3}$-free and $K_{5}$ free graphs [5]. We assign weights to the edges of
the graph $G^{\prime}$ depending upon the height of the bag they are
associated with. The weights assigned to them are exponential in the height of
the bags. Therefore, we need the height of a bag to be $O(\log n)$ to obtain a
polynomially bounded weight function. Hence similar to [5], we define an
auxiliary tree $A(T^{\prime})$ of the tree $T^{\prime}$. In some sense,
$A(T^{\prime})$ is a balanced representation of $T^{\prime}$, therefore the
height of $A(T^{\prime})$ is $O(\log n)$. Nodes in $A(T^{\prime})$ are the
same as $T^{\prime}$, i.e. the bags of $T^{\prime}$, but the edges between the
bags are inserted differently. The weight of an edge of $G^{\prime}$
associated with a bag $B$ of $T^{\prime}$ depends upon the height of the bag
$B$ in $A(T^{\prime})$.

#### Auxiliary Tree:

In order to construct the auxiliary tree from $T^{\prime}$, first, we find a
node called center node $c(T^{\prime})$. Make this node the root of the
$A(T^{\prime})$. Let $T_{1},T_{2},\ldots,T_{l}$ be the subtrees obtained by
deleting $c(T^{\prime})$ from $T^{\prime}$. Recursively apply the same
procedure on these subtrees and make $c(T_{1}),c(T_{2}),\ldots,c(T_{l})$
children of $c(T)$. If $c(T)$ shares a separating set $\tau$ with $T_{i}$ then
$c(T_{i})$ is said to be attached at $\tau$ with $c(T)$. Center nodes are
chosen in such a way that the resultant tree $A(T^{\prime})$ has height
$O(\log n)$. Readers are referred to Section 3.3 of Arora et al. [5] to see
the logspace construction of $A(T^{\prime})$. We use the same construction
here. The height of the root of $A(T^{\prime})$ is defined as the number of
nodes in the longest path from the root $c(T)$ to a leaf node. The heights of
other nodes are one less than that of their parent. From now on, we work with
$A(T^{\prime})$. We use the following two properties of the auxiliary tree.

  1. (i)

Height of a node in $A(T^{\prime})$ is $O(\log n)$.

  2. (ii)

If ${\tilde{T}}$ is a subtree of $T^{\prime}$, then there exists a bag $B$ in
$\tilde{T}$ such that all the other bags of $\tilde{T}$ are descendants of $B$
in $A(T^{\prime})$.

Now we define the weight function $w^{\prime}$ for the graph $G^{\prime}$.
Note that the graph induced by the set of edges associated with a bag $B_{i}$
is either planar or constant size; we call these the components of
$G^{\prime}$. $w^{\prime}$ is a linear combination of two weight functions
$w_{1}$ and $w_{2}$. $w_{1}$ gives nonzero circulation to those cycles which
are completely contained within a component, and $w_{2}$ gives nonzero
circulation to those cycles which span over at least two components. We define
$w_{1}$ and $w_{2}$ separately for planar and constant size components. Let
$G^{\prime}_{B_{i}}$ be the graph induced by the set of edges associated with
the bag $B_{i}$. Let $K$ be a constant such that $K>max(2^{m+2},7)$, where $m$
is the maximum number of edges associated with any constant size component.

####  If $G^{\prime}_{B_{i}}$ is a planar component:

$w_{1}$ for such components is same as the weight function defined in [6] for
planar graphs. We know that given a planar graph $G$, its planar embedding can
be computed in logspace [1].

######  Theorem 3.3 ([6]).

Given a planar embedding of a graph $H$, there exists a logspace computable
function $w$ such that for every cycle $C$ of $H$, circulation of the cycle
$w(C)\neq 0$.

The above weight function gives nonzero circulation to every cycle that is
completely contained in a planar component.

The weight function $w_{2}$ for planar components is defined as follows.
$w_{2}$ assigns weights to only those faces of the component, which are
adjacent to some separating set. For a subtree of $T_{s}$ of $A(T^{\prime})$,
let $l(T_{s})$ and $r(T_{s})$ denote the number of leaf nodes in $T_{s}$ and
root node of $T_{s}$, respectively. For a bag $B_{i}$, $h(B_{i})$ denotes the
height of the bag in $A(T^{\prime})$. If $B_{i}$ is the only bag in the
subtree rooted at $B_{i}$, then each face in $G^{\prime}_{B_{i}}$ is assigned
weight zero. Otherwise, let $\tau$ be a separating set where some subtree
$T_{i}$ is attached to $B_{i}$. The faces adjacent to $\tau$ in
$G^{\prime}_{B_{i}}$ are assigned weight $2\times K^{h(r(T_{i}))}\times
l(T_{i})$. If a face is adjacent to more than one separating set, then the
weight assigned to the face is the sum of the weights due to each separating
set. The weight of a face is defined as the sum of the weights of the edges of
the face in clockwise order. If we have a skew-symmetric weight function, then
the weight of the clockwise cycle will be the sum of the weights of the faces
inside the cycle [6]. Therefore assigning positive weights to every face
inside a cycle will ensure that the circulation of the cycle is nonzero. Given
weights on the faces of a graph, we can obtain weights for the edges so that
the sum of the weights of the edges of a face remains the same as the weight
of the face assigned earlier [23].

#### If $G^{\prime}_{B_{i}}$ is a constant size component:

For this type of component, we need only one weight function. Thus we set
$w_{2}$ to be zero for all the edges in $G^{\prime}_{B_{i}}$ and $w_{1}$ is
defined as follows. Let $e_{1},e_{2},\ldots,e_{k}$ be the edges in the
component $Q_{i}$, for some $k\leq m$. Edge $e_{j}$ is assigned weight
$2^{i}\times K^{h(r(T_{i}))-1}\times l(T_{i})$ (for some arbitrarily fixed
orientation), Where $T_{i}$ is the subtree of $A(T^{\prime})$ rooted at
$B_{i}$. Note that for any subset of edges of $G^{\prime}_{B_{i}}$, the sum of
the weight of the edges in that subset is nonzero with respect to $w_{1}$.

The final weight function is $w^{\prime}=\langle w_{1}+w_{2}\rangle.$ Since
the maximum height of a bag in $A(T^{\prime})$ is $O(\log n)$, the weight of
an edge is at most $O(n^{c})$, for some constant $c>0$.

######  Lemma 3.4.

For a cycle $C$ in $G^{\prime}$ sum of the weights of the edges of $C$
associated with the bags in a subtree $T_{i}$ of $A(T^{\prime})$ is
$<K^{h(r(T_{i}))}\times l(T_{i})$.

######  Proof 3.5.

Let $w(C_{T_{i}})$ denotes the sum of the weight of the edges of a cycle $C$
associated with the bags in $T_{i}$. We prove the Lemma by induction on the
height of the root of the subtrees of $A(T^{\prime})$. Note that the Lemma
holds trivially for the base case when the height of the root of a subtree is
$1$.

Induction hypothesis: Assume that it holds for all the subtrees such that the
height of their root is $<h(r(T_{i}))$.

Now we will prove it for $T_{i}$. Let $T_{i}^{1},T_{i}^{2},\ldots,T_{i}^{k}$
be the subtrees attached to $r(T_{i})$.

  * •

First, consider the case when $G^{\prime}_{r(T_{i})}$ is a constant size
graph: In this case, we know that the sum of the weights of the edges of $C$
associated with $r(T_{i})$ is $\leq\sum_{j=1}^{m}2^{j}\times
K^{h(r(T_{i}))-1}\times l(T_{i})$ and by the induction hypothesis, we know
that $w(C_{T_{i}^{j}})<K^{h(r(T_{i}^{j}))}\times l(T_{i}^{j})$, for all
$j\in[k]$. Therefore,

$\displaystyle w(C_{T_{i}})$ $\displaystyle\leq$
$\displaystyle\sum_{j=1}^{m}2^{j}\times K^{h(r(T_{i}))-1}\times
l(T_{i})+\sum_{j=1}^{k}K^{h(r(T_{i}^{j}))}\times l(T_{i}^{j})$ $\displaystyle
w(C_{T_{i}})$ $\displaystyle\leq$ $\displaystyle(2^{m+1}-1)\times
K^{h(r(T_{i}))-1}\times l(T_{i})+K^{h(r(T_{i}))-1}\times l(T_{i})$
$\displaystyle w(C_{T_{i}})$ $\displaystyle\leq$
$\displaystyle(2^{m+1})\times(K^{h(r(T_{i}))-1}\times l(T_{i}))\hskip
113.81102pt[K>2^{m+2}]$ $\displaystyle w(C_{T_{i}})$ $\displaystyle<$
$\displaystyle K^{h(r(T_{i}))}\times l(T_{i})$

  * •

When $G^{\prime}_{r(T_{i})}$ is a planar graph: let
$\tau_{1},\tau_{2},\ldots,\tau_{k}$ be the separating sets present in
$G^{\prime}_{r(T_{i})}$ such that the subtree $T_{i}^{j}$ is attached to
$r(T_{i})$ at $\tau_{j}$, for all $j\in[k]$. A separating set can be present
in at most 3 faces. Thus it can contribute $2\times 3\times
K^{h(r(T_{i}^{j}))}\times l(T_{i}^{j})$ to the circulation of the cycle $C$.
Therefore,

$\displaystyle w(C_{T_{i}})$ $\displaystyle\leq$
$\displaystyle\sum_{j=1}^{k}6\times K^{h(r(T_{i}^{j}))}\times
l(T_{i}^{j})+\sum_{j=1}^{k}K^{h(r(T_{i}^{j}))}\times l(T_{i}^{j})$
$\displaystyle w(C_{T_{i}})$ $\displaystyle\leq$ $\displaystyle 7\times
K^{h(r(T_{i}))-1}\times l(T_{i})\hskip 142.26378pt[K>7]$ $\displaystyle
w(C_{T_{i}})$ $\displaystyle<$ $\displaystyle K^{h(r(T_{i}))}\times l(T_{i})$

######  Lemma 3.6.

For a cycle, $C$ in $G$ let $B_{i}$ be the unique highest bag in
$A(T^{\prime})$ that have some edges of $C$ associated with it. Then the sum
of the weights of the edges of $C$ associated with $B_{i}$ will be more than
that of the rest of the edges of $C$ associated with the other bags.

######  Proof 3.7.

Let $T_{i}$ be the subtree of $A(T^{\prime})$ rooted at $B_{i}$. We know that
sum of the weights of the edges of $C$ associated $B_{i}$ is $\geq 2\times
K^{h(r(T_{i}))-1}\times l(T_{i})$. Let $T_{i}^{1},T_{i}^{2},\ldots,T_{i}^{k}$
be the subtree of $T_{i}$ rooted at children of $B_{i}$. By Lemma 3.4, we know
that the sum of the weight of the edges of $C$ associated with the bags in
these subtrees is $<\sum_{j=1}^{k}K^{h(r(T_{i}^{j}))}\times
l(T_{i}^{j})=K^{h(r(T_{i}))-1}\times l(T_{i})$. Therefore, the lemma follows.

######  Lemma 3.8.

Circulation of a simple cycle $C$ in the graph $G^{\prime}$ is nonzero with
respect to $w^{\prime}$.

######  Proof 3.9.

If $C$ is contained within a component, i.e., its edges are associated with a
single bag $B_{i}$, then we know that $w_{1}$ assigns nonzero circulation to
$C$. Suppose the edges of $C$ are associated with more than one bag in
$T^{\prime}$. By Claim 2, we know that these bags form a connected component.
By the (ii) property of $A(T^{\prime})$, we know that there is a unique
highest bag $B_{i}$ in $A(T^{\prime})$ which have edges of $C$ associated with
it. Therefore from Lemma 3.6 we know that the circulation of $C$ will be
nonzero.

######  Proof 3.10 (Proof of Theorem 1.1).

Proof of Theorem 1.1 follows from Lemma 3.2 and 3.8.

##  4 Maximum Matching

In this section, we consider the complexity of the maximum matching problem in
single crossing minor free graphs. Recently Datta et al. [8] have shown that
the bipartite maximum matching can be solved in in the planar, bounded genus,
$K_{3,3}$-free and $K_{5}$-free graphs.

Their techniques can be extended to any graph class where nonzero circulation
weights can be assigned in logspace. For constructing a maximum matching in
$K_{3,3}$-free and $K_{5}$-free bipartite graphs, they use the logspace
algorithm of [5] as a black box. Since from Theorem 1.1 nonzero circulation
weights can be computed for the more general class of any single crossing
minor free graphs, we get the bipartite maximum matching result of Corollary
1.2.

In a related work recently, Eppstein and Vazirani [16] have shown an $\NC$
algorithm for the case when the graph is not necessarily bipartite. However,
the result holds only for constructing perfect matchings. In non-bipartite
graphs, there is no known parallel (e.g., ) or space-efficient algorithm for
deterministically constructing a maximum matching even in the case of planar
graphs [30, 8]. Datta et al. [8] givelo an approach to design a _pseudo-
deterministic_ algorithm for this problem. Pseudo-deterministic algorithms are
probabilistic algorithms for search problems that produce a unique output for
each given input with high probability. That is, they return the same output
for all but a few of the possible random choices. We call an algorithm pseudo-
deterministic $\NC$ if it runs in $\RNC$ and is pseudo-deterministic.

Using the Gallai-Edmonds decomposition theorem, [8] shows that the search
version of the maximum matching problem reduces to determining the size of the
maximum matching in the presence of algorithms to (a) find a perfect matching
and to (b) solve the bipartite version of the maximum matching, all in the
same class of graphs. This reduction implies a pseudo-deterministic $\NC$
algorithm as we only need to use randomization for determining the size of the
matching, which always returns the same result. For single crossing minor free
graphs, using the $\NC$ algorithm of [16] for finding a perfect matching and
our $\SPL$ algorithm for finding a maximum matching in bipartite graphs, we
have the following result:

######  Theorem 4.1.

Maximum matching in single-crossing minor free graphs (not necessarily
bipartite) is in pseudo-deterministic .

##  5 Conclusion

We have given a construction of a nonzero circulation weight function for the
class of graphs that can be expressed as 3-clique-sums of planar and constant
treewidth graphs. However, it seems that our technique can be extended to the
class of graphs that can be expressed as 3-clique-sums of constant genus and
constant treewidth graphs. Further extending our results to larger graph
classes would require fundamentally new techniques. This is so because the
most significant bottleneck in parallelizing matching algorithms for larger
graph classes such as apex minor free graphs or $H$-minor free graphs for a
finite $H$ is the absence of a parallel algorithm for the structural
decomposition of such families. Thus we would need to revisit the Robertson-
Seymour graph minor theory to parallelize it. This paper thus serves the dual
purpose of delineating the boundaries of the known regions of parallel
(bipartite) matching and reachability and as an invitation to the vast unknown
of parallelizing the Robertson-Seymour structure theorems.

## References

  * [1] Eric Allender and Meena Mahajan.  The complexity of planarity testing.  Information and Computation, 189:117–134, 2004.
  * [2] Eric Allender, Klaus Reinhardt, and Shiyu Zhou.  Isolation, matching, and counting: Uniform and nonuniform upper bounds.  Journal of Computer and System Sciences, 59:164–181, 1999.
  * [3] Nima Anari and Vijay V. Vazirani.  Matching is as easy as the decision problem, in the NC model.  In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, volume 151 of LIPIcs, pages 54:1–54:25. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [4] Nima Anari and Vijay V. Vazirani.  Planar graph perfect matching is in nc.  J. ACM, 67(4), May 2020.  doi:10.1145/3397504.
  * [5] Rahul Arora, Ashu Gupta, Rohit Gurjar, and Raghunath Tewari.  Derandomizing isolation lemma for $k_{3,3}$-free and $k_{5}$-free bipartite graphs.  In 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, France, pages 10:1–10:15, 2016.
  * [6] Chris Bourke, Raghunath Tewari, and N. V. Vinodchandran.  Directed planar reachability is in unambiguous log-space.  ACM Transactions on Computation Theory, 1(1):1–17, 2009.  doi:http://doi.acm.org/10.1145/1490270.1490274.
  * [7] Erin W. Chambers and David Eppstein.  Flows in one-crossing-minor-free graphs.  J. Graph Algorithms Appl., 17(3):201–220, 2013.
  * [8] Samir Datta, Raghav Kulkarni, Ashish Kumar, and Anish Mukherjee.  Planar maximum matching: Towards a parallel algorithm.  In Wen-Lian Hsu, Der-Tsai Lee, and Chung-Shou Liao, editors, 29th International Symposium on Algorithms and Computation, ISAAC 2018, December 16-19, 2018, Jiaoxi, Yilan, Taiwan, volume 123 of LIPIcs, pages 21:1–21:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.  URL: https://doi.org/10.4230/LIPIcs.ISAAC.2018.21, doi:10.4230/LIPIcs.ISAAC.2018.21.
  * [9] Samir Datta, Raghav Kulkarni, and Sambuddha Roy.  Deterministically isolating a perfect matching in bipartite planar graphs.  Theory Comput. Syst., 47(3):737–757, 2010.
  * [10] Samir Datta, Raghav Kulkarni, Raghunath Tewari, and N.V. Vinodchandran.  Space complexity of perfect matching in bounded genus bipartite graphs.  Journal of Computer and System Sciences, 78(3):765 – 779, 2012\.  In Commemoration of Amir Pnueli.  doi:https://doi.org/10.1016/j.jcss.2011.11.002.
  * [11] Samir Datta, Pankaj Kumar, Anish Mukherjee, Anuj Tawari, Nils Vortmeier, and Thomas Zeume.  Dynamic complexity of reachability: How many changes can we handle?  In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), pages 122:1–122:19, 2020.
  * [12] Erik D. Demaine, Mohammad Taghi Hajiaghayi, Naomi Nishimura, Prabhakar Ragde, and Dimitrios M. Thilikos.  Approximation algorithms for classes of graphs excluding single-crossing graphs as minors.  J. Comput. Syst. Sci., 69(2):166–195, 2004.
  * [13] Edsger W. Dijkstra.  A note on two problems in connexion with graphs.  Numerische Mathematik, 1:269–271, 1959.
  * [14] Jack Edmonds.  Paths, trees and flowers.  Canadian Journal Of Mathematics, pages 449–467, 1965.
  * [15] Michael Elberfeld, Andreas Jakoby, and Till Tantau.  Logspace versions of the theorems of bodlaender and courcelle.  In FOCS ’10: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, 2010.
  * [16] David Eppstein and Vijay V. Vazirani.  NC algorithms for computing a perfect matching and a maximum flow in one-crossing-minor-free graphs.  SIAM J. Comput., 50(3):1014–1033, 2021.
  * [17] Stephen A. Fenner, Rohit Gurjar, and Thomas Thierauf.  Bipartite perfect matching is in Quasi-NC.  In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 754–763, 2016.
  * [18] L. R. Ford, Jr. and D. R. Fulkerson.  Maximal flow through a network.  Canadian Journal of Mathematics, 8:399–404, 1956.  doi:https://doi.org/10.4153/CJM-1956-045-5.
  * [19] Chetan Gupta, Vimal Raj Sharma, and Raghunath Tewari.  Reachability in O(log n) Genus Graphs is in Unambiguous Logspace.  In 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany, pages 34:1–34:13, 2019.
  * [20] Chetan Gupta, Vimal Raj Sharma, and Raghunath Tewari.  Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs.  In Javier Esparza and Daniel Krá?, editors, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), volume 170 of Leibniz International Proceedings in Informatics (LIPIcs), pages 43:1–43:13, Dagstuhl, Germany, 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik.
  * [21] Vivek Anand T. Kallampally and Raghunath Tewari.  Trading determinism for time in space bounded computations.  In 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26, 2016 - Kraków, Poland, pages 10:1–10:13, 2016.
  * [22] Richard M. Karp, Eli Upfal, and Avi Wigderson.  Constructing a perfect matching is in random NC.  In Robert Sedgewick, editor, Proceedings of the 17th Annual ACM Symposium on Theory of Computing, May 6-8, 1985, Providence, Rhode Island, USA, pages 22–32. ACM, 1985.
  * [23] Arpita Korwar.  Matching in planar graphs.  Master’s thesis, IITK, 2009.
  * [24] Jan Kynčl and Tomáš Vyskočil.  Logspace reduction of directed reachability for bounded genus graphs to the planar case.  ACM Transactions on Computation Theory, 1(3):1–11, 2010.  doi:http://doi.acm.org/10.1145/1714450.1714451.
  * [25] Meena Mahajan and Kasturi R. Varadarajan.  A new nc-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract).  In Proceedings of the Thirty-second Annual ACM Symposium on Theory of Computing, STOC ’00, pages 351–357, New York, NY, USA, 2000. ACM.  doi:10.1145/335305.335346.
  * [26] Gary L. Miller and Joseph Naor.  Flow in planar graphs with multiple sources and sinks.  SIAM Journal on Computing, 24:1002–1017, 1995.
  * [27] Ketan Mulmuley, Umesh V. Vazirani, and Vijay V. Vazirani.  Matching is as easy as matrix inversion.  In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA, pages 345–354, 1987.
  * [28] Klaus Reinhardt and Eric Allender.  Making nondeterminism unambiguous.  SIAM J. Comput., 29(4):1118–1131, 2000.
  * [29] Neil Robertson and Paul D. Seymour.  Excluding a graph with one crossing.  In Graph Structure Theory, Proceedings of a AMS-IMS-SIAM Joint Summer Research Conference on Graph Minors, June 22 to July 5, 1991, Seattle, USA, pages 669–675, 1991.
  * [30] Piotr Sankowski.  NC algorithms for weighted planar perfect matching and related problems.  In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 97:1–97:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  * [31] Simon Straub, Thomas Thierauf, and Fabian Wagner.  Counting the number of perfect matchings in $K_{5}$-free graphs.  Theory Comput. Syst., 59(3):416–439, 2016.
  * [32] Ola Svensson and Jakub Tarnawski.  The matching problem in general graphs is in Quasi-NC.  In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, pages 696–707. IEEE Computer Society, 2017.
  * [33] Raghunath Tewari and N. V. Vinodchandran.  Green’s theorem and isolation in planar graphs.  Inf. Comput., 215:1–7, 2012.
  * [34] Thomas Thierauf and Fabian Wagner.  Reachability in ${K}_{3,3}$-free Graphs and ${K}_{5}$-free Graphs is in Unambiguous Log-Space.  In 17th International Conference on Foundations of Computation Theory (FCT), Lecture Notes in Computer Science 5699, pages 323–334. Springer-Verlag, 2009.
  * [35] Thomas Thierauf and Fabian Wagner.  The isomorphism problem for planar 3-connected graphs is in unambiguous logspace.  Theory Comput. Syst., 47(3):655–673, 2010.

##  Appendix A Appendix

######  Proof A.1 (Proof of Lemma 3.2).

To construct the weight function $w$, we associate a sequence $P(u,v)$ of
edges of $G^{\prime}$ with each edge $(u,v)$ of $G$. Assume that $T^{\prime}$
is a rooted tree, and root is the highest node in the tree. The heights of all
the other nodes are one less than that of their parent. As we mentioned that
$T^{\prime}$ is a tree decomposition of $G$. For an edge $(u,v)$, we know that
there are unique highest bags $B_{1}$ and $B_{2}$ that contain vertices $u$
and $v$, respectively.

  * •

If $B_{1}=B_{2}$ then $P(u,v)=(u_{B_{1}},v_{B_{2}})$.

  * •

If $B_{1}$ is an ancestor of $B_{2}$ then
$P(u,v)=(u_{B_{1}},u_{parent(\cdots(parent(B_{2})))}),\ldots,(u_{parent(B_{2})},u_{B_{2}}),(u_{B_{2}},v_{B_{2}})$.

  * •

If $B_{1}$ is a descendant of $B_{2}$ then
$P(u,v)=(u_{B_{1}},v_{B_{1}}),(v_{B_{1}},v_{parent(B_{1})}),\ldots,(v_{parent(\cdots(parent(B_{1})))},v_{B_{2}})$.

The weight function $w$ for the graph $G$ is defined as follows:

$\displaystyle w(u,v)=\sum_{e\in P(u,v)}w^{\prime}(e)$

For a simple cycle $C=e_{1},e_{2},\ldots,e_{j}$ in $G$, we define
$P(C)=P(e_{1}),P(e_{2}),\ldots,P(e_{j})$. Note that $P(C)$ is a closed walk in
$G^{\prime}$. Let $E^{\prime}_{d}(C)$ be the subset of edges of $G^{\prime}$
such for all edges $e\in E^{\prime}_{d}(C)$ both $e$ and $e^{r}$ appear in
$P(C)$, where $e^{r}$ denotes the edge obtained by reversing the direction of
$e$. We prove that if we remove the edges of $E^{\prime}_{d}(C)$ from $P(C)$
then the remaining edges $P(C)-E^{\prime}_{d}(C)$ form a simple cycle in
$G^{\prime}$.

######  Claim 3.

Edges in the set $P(C)-E^{\prime}_{d}(C)$ form a simple cycle in $G^{\prime}$.

######  Proof A.2.

Note that the lemma follows trivially if $P(C)$ is a simple cycle. Therefore,
assume that $P(C)$ is not a simple cycle. We start traversing the walk $P(C)$
starting from the edges of the sequence $P(e_{1})$. Let $P(e_{k})$ be the
first place where a vertex in the walk $P(e_{1})P(e_{2}).....P(e_{k})$
repeats, i.e., edges in the sequence $P(e_{1})P(e_{2}).....P(e_{k-1})$ form a
simple path, but after adding the edges of $P(e_{k})$ some vertices are
visited twice in the walk $P(e_{1})P(e_{2}).....P(e_{k-1})P(e_{k})$ for some
$k\leq j$. This implies that some vertices are visited twice in the sequence
$P(e_{k-1})P(e_{k})$. Let $e_{k-1}=(u,v)$ and $e_{k}=(v,x)$. This implies that
some copies of the vertex $v$ appear twice in the sequence $P(u,v)P(v,x)$. Let
$B_{1}$ and $B_{2}$ be the highest bags such that $B_{1}$ contains the copies
of vertices $u$ and $v$, and $B_{2}$ contains the copies of $v$ and $x$. Let
bag $B$ be the lowest common ancestor of $B_{1}$ and $B_{2}$. We know that $B$
must contain a copy of the vertex $v$, i.e., $v_{B}$. Let $B^{\prime}$ be the
highest bag containing a copy of vertex $v$, i.e., $v_{B^{\prime}}$. First,
consider the case when neither $B_{1}$ is an ancestor of $B_{2}$ and vice-
versa, other cases can be handled similarly. In that case sequence
$P(u,v)=u_{B_{1}}v_{B_{1}}v_{parent(B_{1})}\ldots v_{B}\ldots v_{B^{\prime}}$
and $P(v,w)=v_{B^{\prime}}\ldots v_{B}\ldots
v_{parent(B_{2})}v_{B_{2}}w_{B_{2}}$. Note that in $P(u,v)$ a path goes from
$v_{B}$ to $v_{B^{\prime}}$ and the same path appear in reverse order from
$v_{B^{\prime}}$ to $v_{B}$ in the sequence $P(v,x)$. Therefore if we remove
these two paths from $P(u,v)$ and $P(v,w)$ the remaining subsequence of the
sequence $P(u,v)P(v,w)$ will be a simple path, i.e., no vertex will appear
twice since $B$ is the lowest common ancestor of $B_{1}$ and $B_{2}$. Now
repeat this procedure for $P_{k+1},P_{k_{2}}\ldots$ and so on till $P_{k}$. In
the end, we will obtain a simple cycle.

Since we assumed that the weight function $w^{\prime}$ is skew-symmetric, we
know that $w^{\prime}(e)=-w(e^{r})$, for all $e\in G^{\prime}$. This implies
that $w^{\prime}(E^{\prime}_{d}(C))=0$. Therefore
$w(C)=w^{\prime}(P(C))=w^{\prime}(P(C)-E^{\prime}_{d}(C))$. From Claim 3 we
know that edges in the set $P(C)-E^{\prime}_{d}(C)$ form a simple cycle and we
assumed that $w^{\prime}$ gives nonzero circulation to every simple cycle
therefore, $w^{\prime}(P(C)-E^{\prime}_{d}(C))\neq 0$. This implies that
$w(C)\neq 0$. This finishes the proof of Lemma 3.2.

######  Proof A.3 (Proof of Claim 2).

Note that if we treat each vertex in the bags of $T^{\prime}$ distinctly, then
there is a one-to-one correspondence between vertices of $G^{\prime}$ and
vertices in the bags of $T^{\prime}$. Therefore, in $T^{\prime}$ a vertex of
$G^{\prime}$ is identified by its corresponding vertex. Note that all the bags
which contain vertices of the cycle $C$ form a connected component in
$T^{\prime}$. We will now prove that if a bag $B$ contains some vertices of
$C$, then either $B$ has some edges of $C$ associate with it or no bag in the
subtree rooted at $B$ has any edge of $C$ associated with it. From this, we
can conclude that the bags which have some edges of $C$ associated with them
form a connected component in $T^{\prime}$.

Assume that $B$ is a bag which contains a vertex of $C$ but no edge of $C$ is
associated with it. This implies that $C$ never enters in any of the children
of $B$. Because, let us assume it enters to some child $B^{\prime}$ of $B$
through some vertex $v_{B^{\prime}}$ of $B^{\prime}$. In that case, there will
be an edge $(v_{B},v_{B^{\prime}})$ of $C$ associated with the bag $B$, which
is a contradiction. Therefore subtree rooted at $B$ will not have any edge of
the cycle $C$ associated with it. This finishes the proof.