Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs

Introduction

The perfect matching problem and its variations are one of the most well-studied problems in theoretical computer science. Research in understanding the inherent complexity of computational problems related to matching has lead to important results and techniques in complexity theory and elsewhere in theoretical computer science. However, even after decades of research, the exact complexity of many problems related to matching is not yet completely understood.

We investigate the space complexity of certain well studied perfect matching problems over bipartite graphs. We prove new uniform space complexity upper bounds on these problems for graphs embedded on surfaces of constant genus. We prove our upper bounds by solving the technical problem of ‘deterministically isolating’ a perfect matching for this class of graphs.

Distinguishing a single solution out of a set of solutions is a basic algorithmic problem with many applications. The isolating lemma due to Mulmulay, Vazirani, and Vazirani provides a general randomized solution to this problem. Let ${\cal F}$ be a non-empty set system on $U=\{1,\ldots,n\}$. The isolating lemma says, for a random weigh function on $U$ (bounded by $n^{O(1)}$), with high probability there is a unique set in ${\cal F}$ of minimum weight [MVV87]. This lemma was originally used to give an elegant \RNC algorithm for constructing a maximum matching (by isolating a minimum weight perfect matching) in general graphs. Since its discovery, the isolating lemma has found many applications, mostly in discovering new randomized or non-uniform upper bounds, via isolating minimum weight solutions [MVV87, RA00, GW96, ARZ99]. Clearly, derandomizing the isolating lemma in sufficient generality will improve these upper bounds to their deterministic counterparts and hence will be a major result. Unfortunately, recently it is shown that such a derandomization will imply certain circuit lower bounds and hence is a difficult task [AM08].

Can we bypass isolating lemma altogether and deterministically isolate minimum weight solutions in specific situations? Recent results illustrate that one may be able to use the structure of specific computational problem under consideration to achieve non-trivial deterministic isolation. In [BTV09], the authors used the structure of directed paths in planar graphs to prescribe a simple weight function that is computable deterministically in logarithmic space with respect to which the minimum weight directed path between any two vertices is unique. In [DKR08], the authors isolated a perfect matching in planar bipartite graphs. In this paper we extend the deterministic isolation technique of [DKR08] to isolate a minimum weight perfect matching in bipartite graphs embedded on constant genus surfaces.

Let $G$ be a bipartite graph with weight function $w$ on it edges. For an even cycle $C=e_{1}e_{2}\cdots e_{2k}$, the circulation of $C$ with respect to $w$ is the sum $\sum_{i=1}^{2k}(-1)^{i}w(e_{i})$. The main technical contribution of the present paper can be stated (semi-formally) as follows.

Main Technical Result. There is a logspace matching preserving reduction $f$, and a logspace computable and polynomially bounded weight function $w$, so that given a bipartite graph $G$ with a combinatorial embedding on a surface of constant genus, the circulation of any simple cycle in $f(G)$ with respect to $w$ is non-zero. (This implies that the minimum weight perfect matching in $f(G)$ is unique [DKR08]).

We use this result to establish (using known techniques) the following new upper bounds. Refer to the next section for definitions.

New Upper Bounds. For bipartite graphs, combinatorially embedded on surfaces of constant genus the problems \isMatch and \isUniqueMatch are in \SPL, and the problem \constructMatch is in $\FL^{\SPL}$.

is a logspace complexity class that was first studied by Allender, Reinhardt, and Zhou [ARZ99]. This is the class of problems reducible to the determinant with the promise that the determinant is either 0 or 1. In [ARZ99], the authors show, using a non-uniform version of isolating lemma, that perfect matching problem for general graphs is in a ‘non-uniform’ version of \SPL. In [DKR08], using the above-mentioned deterministic isolation, the authors show that for planar bipartite graphs, \isMatch is in fact in \SPL (uniformly). Recently, Hoang showed that for graphs with polynomially many matchings, perfect matchings and many related matching problems are in \SPL [Hoa09]. \SPL is contained in logspace counting classes such as $\modkl$ for all $k\geq 2$ (in particular in $\oplus\L$), \PL, and $\ceql$, which are in turn contained in $\NC^{2}$. Thus the upper bound of \SPL that we prove implies that the problems \isMatch and \isUniqueMatch for the class of graphs we study are in these logspace counting classes as well.

The techniques that we use in this paper can also be used to isolate directed paths in graphs on constant genus surfaces. This shows that the reachability problem for this class of graphs can be decided in the unambiguous class $\UL$, extending the results of [BTV09]. But this upper bound is already known since recently Kynčl and Vyskočil show that reachability for bounded genus graphs logspace reduces to reachability in planar graphs [KV09].

Matching problems over graphs of low genus have been of interest to researchers, mainly from a parallel complexity viewpoint. The matching problems that we consider in this paper are known to be in \NC. In particular in [KMV08], the authors present an $\NC^{2}$ algorithm for computing a perfect matching for bipartite graphs on surfaces of $O(\log n)$ genus (readers can also find an account of known parallel complexity upper bounds for matching problems over various classes of graphs in their paper). However, the space complexity of matching problems for graphs of low genus has not been investigated before. The present paper takes a step in this direction.

Proof Outline. We assume that the graph $G$ is presented as a combinatorial embedding on a surface (orientable or non-orientable) of genus $g$, where $g$ is a constant. This is a standard assumption when dealing with graphs on surfaces, since it is NP-complete to check whether a graph has genus $\leq g$ [Tho89]. We first give a sequence of two reductions to get, from $G$, a graph $G^{\prime}$ with an embedding on a genus $g$ ‘polygonal schema in normal form’. These two reductions work for both orientable and non-orientable cases. At this point we take care of the non-orientable case by reducing it to the orientable case. Once we have the embedding on an orientable polygonal schema in normal form, we further reduce $G^{\prime}$ to $G^{\prime\prime}$ where $G^{\prime\prime}$ is embedded on a constant genus ‘grid graph’. These reductions are matching preserving, bipartiteness preserving and computable in logspace. Finally, for $G^{\prime\prime}$, we prescribe a set of $4g+1$ weight functions, $\mathcal{W}=\{w_{i}\}_{1\leq i\leq 4g+1}$, so that for any cycle $C$ in $G^{\prime\prime}$, there is a weight function $w_{i}\in\mathcal{W}$ with respect to which the circulation of $C$ is non-zero. Since $g$ is constant, we can take a linear combination of the elements in $\mathcal{W}$, for example $\sum_{w_{i}\in\mathcal{W}}{w_{i}\times\left(n^{c}\right)^{i}}$ (where $n$ is the number of vertices in the grid) for some fixed constant $c$ (say $c=4$), to get a single weight function with respect which the circulation of any cycle is non-zero.

The intuition behind these weight functions is as follows (for some of the definitions, refer to later sections). The set ${\mathcal{W}}$ is a disjoint union $\mathcal{W}_{1}\cup\mathcal{W}_{2}\cup\{w\}$ of the sets of weight functions $\mathcal{W}_{1}$, $\mathcal{W}_{2}$, and $\{w\}$. Consider a graph $G$ embedded on a fundamental polygon with $2g$ sides. There are two types cycles in $G$: surface separating and surface non-separating. A basic theorem from algebraic topology implies that a surface non-separating cycle will intersect at least one of the sides of the polygon an odd number of times. This leads to $2g$ weight functions in $\mathcal{W}_{1}$ to take care of all the surface non-separating cycles. There are two types of surface separating cycles: (a) ones which completely lie inside the polygon and (b) the ones which cross some boundary. Type (a) cycles behaves exactly like cycles in plane so the weight function $w$ designed for planar graphs works (from [DKR08]). For dealing with cycles of type (b), we first prove that if such a cycle intersects a boundary, it should alternate between ‘coming in’ and ‘going out’. This leads to $2g$ weight functions in $\mathcal{W}_{2}$ which handle all type (b) cycles.

Figure 1 gives a pictorial view of the components involved in the proof of our main technical result.

The rest of the paper is organized as follows. In Section $2$ we give the necessary definitions and state results from earlier work, that we use in this paper. In Section $3$ we state and prove our upper bounds assuming a grid embedding. In Section $4$ we reduce the non-orientable case to the orientable one. In Section $5$ we give matching preserving, logspace reductions from a combinatorial embedding of the graph on a surface of genus $g$, to a grid embedding. In Section $6$ we add proofs of some necessarylemmas and theorems that we use to prove our results.

Preliminaries

We introduce the necessary terminology from algebraic topology. For a more comprehensive understanding of this topic, refer to any standard algebraic topology book such as [Mas91].

A polygonal schema of a surface $\Gamma$, is a polygon with $2g^{\prime}$ directed sides, such that the sides of the polygon are partitioned into $g^{\prime}$ classes, each class containing exactly two sides and glueing the two sides of each equivalence class gives the surface $\Gamma$ (upto homeomorphism). A side in the $i$th equivalence class is labelled $\sigma_{i}$ or $\bar{\sigma_{i}}$ depending on whether it is directed clockwise or anti-clockwise respectively. The partner of a side $\sigma$ is the other side in its equivalence class. By an abuse of notation, we shall sometimes refer to the symbol of a side’s partner, as the partner of the symbol. Frequently we will denote a polygonal schema as a linear ordering of its sides moving in a clockwise direction, denoted by $X$. For a polygonal schema $X$, we shall refer to any polygonal schema which is a cyclic permutation, or a reversal of the symbols, or a complementation ($\sigma$ mapped to $\bar{\sigma}$ and vice versa) of the symbols, as being the same as $X$. A polygonal schema is called orientable (resp. non-orientable) if the corresponding surface is orientable (resp. non-orientable).

An orientable polygonal schema is said to be in normal form if it is in one of the following forms:

A non-orientable polygonal schema is said to be in normal form if it is of one of the following forms:

where, $X$ is a string representing an orientable schema in normal form (i.e. like Form 2.1 or 2.2 above).

We denote the polygonal schema in the normal form of a surface $\Gamma$ as $\Lambda(\Gamma)$. We will refer to two orientable symbols $\sigma,\tau$ which form the following contiguous substring: $\sigma\tau\bar{\sigma}\bar{\tau}$ as being clustered together while a non-orientable symbol $\sigma$ which occurs like $\sigma\sigma$ as a contiguous subtring is said to form a pair. Thus, in the first and third normal forms above all symbols are clustered. The first normal form represents a connected sum of torii and the third of a projective plane and torii. In the fourth normal form all but one of the orientable symbols are clustered while the only non-orientable symbol is sort of clustered with the other orientable symbol. This form represents a connected sum of a Klein Bottle and torii. The second normal form represents a sphere.

An undirected graph $G$ is said to be embedded on a surface $\Gamma$ if it can be drawn on $\Gamma$ so that no two edges cross. We assume that the graph is given with a combinatorial embedding on a surface of constant genus. Refer to the book by Mohar and Thomassen [MT01] for details. A graph $G$ is said to have genus $g$ if $G$ has a minimal embedding (an embedding where every face of $G$ is homeomorphic to a disc) on a genus $g$ surface. Such an embedding is also called a 2-cell embedding. A genus $g$ graph is said to be orientable (non-orientable) if the surface is orientable (non-orientable).

The polygonal schema of a graph $G$ is a combinatorial embedding given on the polygonal schema of some surface $\Gamma$ together with the ordered set of vertices on each side of the polygon. Formally it is a tuple $(\phi,\mathcal{S})$, where $\phi$ is a cyclic ordering of the edges around a vertex and $\mathcal{S}=(S_{1},S_{2},\ldots,S_{2g})$ is the cyclic ordering of the directed sides of the polygon. Each $S_{i}$ is an ordered sequence of the vertices, from the tail to the head of the side $S_{i}$. Moreover every $S_{i}$ is paired with some other side, say $S_{i}^{-1}$ in $\mathcal{S}$, such that the $j$th vertex of $S_{i}$ (say from the tail of $S_{i}$) is the same as the $j$th vertex of $S_{i}^{-1}$ (form the tail of $S_{i}^{-1}$).

2 Complexity Theory

For a nondeterministic machine $M$, let ${\it acc}_{M}(x)$ and ${\it rej}_{M}(x)$ denote the number of accepting computations and the number of rejecting computations respectively. Denote ${\it gap}_{M}(x)={\it acc}_{M}(x)-{\it rej}_{M}(x)$.

A language $L$ is in $\SPL$ if there exists a logspace bounded nondeterministic machine $M$ so that for all inputs $x$, ${\it gap}_{M}(x)\in\{0,1\}$ and $x\in L$ if and only if ${\it gap}_{M}(x)=1$. $\FL^{\SPL}$ is the class of functions computed by a logspace machine with an \SPL oracle. \UL is the class of languages $L$, decided by a nondeterministic logspace machine (say $M$), such that for every string in $L$, $M$ has exactly one accepting path and for a string not in $L$, $M$ has no accepting path.

Alternatively, we can define \SPL as the class of problems logspace reducible to the problem of checking whether the determinant of a matrix is or not under the promise that the determinant is either or $1$. For definitions of other complexity classes refer to any standard textbooks such as [AB09, Vol99]. All reductions discussed in this paper are logspace reductions.

Given an undirected graph $G=(V,E)$, a matching $M$ is a subset of $E$ such that no two edges in $M$ have a vertex in common. A maximum matching is a matching of maximum cardinality. $M$ is said to be a perfect matching if every vertex is an endpoint of some edge in $M$.

We define the following computational problems related to matching:

: Given a bipartite graph $G$, checking if $G$ has a perfect matching.

: Given a bipartite graph $G$, constructing a perfect matching, if one exists.

: Given a bipartite graph $G$, checking if $G$ has a unique perfect matching.

3 Necessary Prior Results

For any bipartite graph $G$ and a weight function $w$, if all circulations of $G$ are non-zero, then $G$ has a unique minimum weight perfect matching.

For any weighted graph $G$ assume that the minimum weight perfect matching in $G$ is unique and also for any subset of edges $E^{\prime}\subseteq E$, the minimum weight perfect matching in $G\setminus E^{\prime}$ is also unique. Then deciding if $G$ has a perfect matching is in \SPL. Moreover, computing the perfect matching (in case it exists) is in $\FL^{\SPL}$.

By definition, $g(G)=1$ if $G$ has a perfect matching, else it is .

To compute a perfect matching in $G$, we will construct a logspace transducer that makes several queries to the function $f$ defined above. For a graph $G^{\prime}$ having a unique minimum weight perfect matching (say $M^{\prime}$), the weight of $M^{\prime}$ can be computed by iteratively querying the function $f(G^{\prime},k)$ for values of $k\in W$ in an increasing order, starting from $n\cdot w_{min}$. The value $k$, for which the function outputs a non-zero value for the first time, is the weight of $M^{\prime}$. We denote this weight by $w_{G^{\prime}}$. First compute $w_{G}$. For an $e$ in $G$, define the graph $G^{-e}=G\setminus\{e\}$. Now compute $w_{G^{-e}}$ for every edge $e$ in $G$. Output the edges $e$ for which $w_{G^{-e}}>w_{G}$. The set of outputted edges comprise a perfect matching (in fact the minimum weight perfect matching) because deleting an edge in this set had increased the weight of the minimum weight perfect matching in the resulting graph. ∎

Embedding on a Grid

Given a 2-cell combinatorial embedding of a graph $G$ of constant genus, there is a logspace transducer that constructs a graph $G^{\prime}\in\GG$, such that, there is a perfect matching in $G$ iff there is a perfect matching in $G^{\prime}$. Moreover, given a perfect matching $M^{\prime}$ in $G^{\prime}$, in logspace one can construct a perfect matching $M$ in $G$.

Using Corollary 7 reduce $G$ to a graph $G_{1}$ that has an embedding on the polygonal schema in the normal form. If the schema is non-orientable, then by applying Theorem 18 we get a graph $G_{2}$ along with its embedding on an orientable polygonal schema (need not be in the normal form). Again by Corollary 7, we reduce it to a graph on a polygonal schema in the normal form. Finally we apply Lemma 8, we get the desired graph. ∎

Let $G$ be a graph embedded on a surface, and let $T$ be a spanning tree of $G$. Then there is an edge $e\in E(G)$ such that $T\cup\{e\}$ contains a non-separating cycle.

Notice that in [ABC+09] the graph was required to be embedded on an orientable surface but the proof did not use this requirement.

Given a cycle (or path) $C$ in an embedded graph $G$, define by $G\mbox{\LeftScissors}C$ the graph constructed by “cutting” the edges incident on the cycle from the right. In other words, the neighbors of $u\in C$ (which are not on the cycle) can be partitioned into two sets, arbitrarily called left and right. For every neighbbor $v$ of $u$ which lies to the right of $C$, cut the edge $(u,v)$ into two pieces $(u,x_{uv})$ and $(y_{uv},v)$ where $x_{uv},y_{uv}$ are (new) spurious vertices. We add spurious edges between consecutive spurious vertices along the cut and label all the newly formed spurious edges with the label $L_{C}$ along the left set and $L_{C}^{-1}$ along the right set. (see Figure 2).

Also, if $C$ is a path, its endpoints will lie on two paths. Consider the first path - if the two edges on either side of $C$ on this path have the same label $L_{1}$. This can be broken into two cases - firstly, if the left and right side of this endpoint are the same (in other words, the path is a cycle). In this case, we just keep the same label $L_{1}$. When the left and right side of this endpoint are distinct, we will need to split the label into two or three new labels as detailed below and similarly for the other path and common label $L_{2}$. We will only describe the case when $L_{1},L_{2}$ are both defined - the other cases are similar and simpler.

First assume that $L_{1}\neq L_{2}$ and $L_{1}\neq L_{2}^{-1}$. Then we will split remove labels $L_{1},L_{2}$ and replace them by four new labels say $L^{\prime}_{1,C},L^{\prime\prime}_{1,C}$ and $L^{\prime}_{2,C},L^{\prime\prime}_{2,C}$, respectively for the two sides of the intersection. If, on the other hand, $L_{1}$ is the same as $L_{2}$ or its inverse - then there are two subcases. Firstly, if the path $C$ is between two copies of the same vertex then we replace $L_{1}$ by two new labels $L^{\prime}_{1,C},L^{\prime\prime}_{1,C}$ one for either side of the cut. $L_{2}$ being a copy or an inverse copy of $L_{1}$ splits automatically. The second case is if $C$ is between two distinct points on two copies or inverse copies. Then we split $L_{1}$ into three parts according to the two points. The rotation system is modified appropriately. We illustrate this in Figure 3.

Notice that in the process of cutting, for every new label $L_{C}$ we are adding at most $4$ new labels.

Given a graph $G_{i}$ embedded on a surface, potentially with spurious edges, we can find $C_{i+1}$, a non-separating cycle (which does not use a spurious edge) by invoking Lemma 4. Define $G_{i+1}$ to be $G_{i}\mbox{\LeftScissors}C_{i+1}$.

Starting with $G_{0}=G$ of genus $g$ and repeating the above operation at most $g$ times, we get a planar graph $H$ with at most $2g$ spurious faces (which consist of spurious vertices and edges).

Now find a spanning tree of this graph which does not use a spurious edge - that such a tree exists follows from noticing that the graph without spurious edges is still connected. Find a tree path connecting any two spurious faces. Cut along this path to combine the two spurious faces into one larger spurious face. Repeat the operation till all the spurious faces are merged into one spurious face and re-embed the planar graph so that it forms the external face.

It is easy to see that the procedure above can be performed in logspace, provided that $g$ is constant. Thus we have sketched the proof of the following:

Given the combinatorial embedding of a constant genus graph we can find a polygonal schema for the graph in logspace.

0.2 Normalizing a Polygonal Schema

We adapt the algorithmic proof of Brahana-Dehn-Heegaard (BDH) [Bra21, DH07] classification theorem as described in Vegter-Yap [VY90] so that it runs in logspace for constant genus graphs. The algorithm starts with a polygonal schema and uses the following five transforms $O(m)$ times to yield a normalized polygonal schema, where the original polygonal schema has $2m$ sides.

Replace $X\sigma\bar{\sigma}$ by $X$ (Example given in Figure 4).

Replace $\sigma\tau X\bar{\tau}Y$ by $\rho X\bar{\rho}\sigma Y$ (Example given in Figure 5).

Replace $\sigma X\sigma Y$ by $\tau\tau Y^{*}X$, where $Y^{*}$ is reverse complement of $Y$ (Example given in Figure 6).

Replace $\sigma X\tau Y\bar{\sigma}U\bar{\tau}V$ by $\rho\pi\bar{\rho}\bar{\pi}UYXV$ (Example given in Figure 7).

Replace $\sigma_{1}\sigma_{1}X\sigma_{2}\sigma_{3}\bar{\sigma_{2}}\bar{\sigma_{3}}Y$ by $\tau_{1}\tau_{1}\tau_{2}\tau_{2}\tau_{3}\tau_{3}XY$ (Example given in Figure 8).

Replace $\sigma\sigma\tau\tau X$ by $\sigma\rho\bar{\sigma}\rho X$ (Example given in Figure 9).

Use reductions A,B,C several times to ensure that all the sides of the polygonal schema have a common endpoint.

Orientable case: Use transform D repeatedly to bring the polygon in normal form.

Use reductions C,D to convert the schema into a form where the orientable symbols are clustered and non-orientable symbols are paired

Use reduction E repeatedly (in the forward direction) to eliminate all orientable symbols.

Use Reduction E in the reverse direction repeatedly to eliminate all but at most one non-orientable symbol.

Use Reduction F, if necessary, to ensure that there is at most one non-orientable symbol.

Possibly, the only step requiring any explanation is the last one. We apply Reduction E in reverse with $X$ as the empty string to replace three non-orientable symbols by two orientable ones forming a cluster of $4$ and a single non-orientable one which forms a pair. The way we apply the reduction, ensures that both the orientable and the non-orientable parts are contiguous.

Fianlly we will be left with a string in one of the first two normal forms or a string of the form $\sigma\sigma\tau\tau X$ (where $X$ is an orientable schema in normal form) in which case Reduction F is applicable.

To see that the above procedure can be carried out in Ł it suffices to prove that each of the above reductions can be carried out in Ł, the number of reductions is bounded by a constant and we can decide in Ł when to carry out a reduction.

The Vegter-Yap paper does careful book-keeping in order to ensure that the number of operations in Step 1 is linear in the original genus. We can alternatively, follow the brute force approach and keep on applying Reductions A,B,C while the sides of the polygon do not have a common end-point. This will require at most linear number of applications of the first two reductions.

Observe that for the orientable case, each application of reduction D reduces the number of unclustered symbols by two. Thus we are done in $O(m)$ applications of this reduction. Similarly, each application of reduction C reduces the number of unpaired non-orientable symbols by one and as before every application of reduction D reduces the number of unclustered orientable symbols by two. So in $O(m)$ steps all the orientable symbols are clustered and the non-orientable symbols are paired. Now every application of reduction E in the forward direction gets rid of two orientable symbols so in $O(m)$ steps all the orientable symbols are removed. Finally $O(m)$ applications of reduction E in reverse lead to removal of all but one non-orientable symbols.

To see that each of the steps is in Ł observe that each of the steps involves one or more of the following operations:

find a path through the interior of the polygon between two points on its boundary

paste two paired sides of (a cut) polygon together

We know how to do the second operation in Ł while the third, being the reverse of the second one is even easier, since we just have to identify corresponding spurious vertices and then excise them out of the corresponding edge. The first operation is just an undirected reachability question in the graph (minus its boundary) hence is in Ł by Reingold’s Theorem.

Finally, a determination of when to apply a particular reduction is easily seen to be in Ł for all but, possibly, reduction D. In this case, for an orientable symbol $\sigma$ separated from its mate $\bar{\sigma}$ on both sides, sequentially test for each other symbol $\tau$ if it lies in one of the two stretches that $\sigma$ and its mate divide the schema into, while its mate $\bar{\tau}$ lies in the other. Having found the first such $\tau$ suffices to enable a use of the reduction.

Thus, using the above argument and Lemma 5 we have sketched the proof of the following theorem:

Given a combinatorial embedding of constant genus, say $g$ (which is positive or otherwise), for a graph $G$, in logspace we can find a polygonal schema for the graph in normal form. of genus $O(|g|)$ in magnitude, and also the corresponding combinatorial embedding.

Let \kGonBi be the class of constant genus, bipartite graphs along with an embedding given on the polygonal schema in normal form of the surface in which the graph has an embedding. Moreover, for every graph in this class, no edge has both its end points on the boundary of the polygon.

At this point, there are no vertices lying on the boundary of the polygonal schema, only edges crossing it. It is easy to see that for each such edge $e=(u,v)$ which has two halves lying on segments of the polygon, if we introduce internal vertices $u^{\prime}=v^{\prime},v^{\prime\prime}$ on the edge (converting it to a path $u,u^{\prime}=v^{\prime},v^{\prime\prime},v$) so that $u^{\prime},v^{\prime}$ lie on the boundary of the polygon on the sides nearer to $u,v$ respectively, then, because the path has odd length the number of perfect matchings in the modified graph is preserved.

Given the combinatorial embedding of a graph of constant genus, there is an logspace reduction, which preserves perfect matchings, to a graph in the class \kGonBi.

0.3 From Polygonal Schema in normal form to a Grid

If $G$ is an orientable graph in \kGonBi, then one can get a logspace, matching-preserving reduction form $G$ to a graph $H\in\GG$

We start with a graph $G\in\kGonBi$ and construct a graph $H\in\GG$ such that the number of perfect matchings in $G$ and $H$ are the same.

We can assume that the maximum degree of $G$ is $3$ and there exists a vertex $s$ of degree $2$ [KMV08]. Think of $G$ as a planar graph. Reduce $G$ to a grid graph $G^{\prime}$ using [ABC+09]. It follows from the reduction that faces are preserved (modulo subdivision of edges). Let $T$ be the spanning tree of $G$ constructed by the algorithm that would be embedded on the course grid and let $T^{\prime}$ be the tree corresponding to $T$ in $G^{\prime}$. Every vertex (say $v$) on boundary of the polygon in $G$ is a leaf node since every edge has at most one of its end points on the boundary of the polygon (by definition of \kGonBi). Therefore $v$ is also a leaf in $T$. Let $s$ be the root of $T$ and $h(u)$ be the height of a vertex $u$ in $T$. It follows from the reduction that $h(u)$ is the value of its $y$-coordinate in $G^{\prime}$.

For the rest of this proof we will use the notation $u^{\prime}$ and $v^{\prime}$ to denote the respective copies of some two vertices $u$ and $v$ in $G$. Now subdivide every horizontal edge in $G^{\prime}$ into $2$ edges to get the grid graph $G^{\prime\prime}$. This ensures that the horizontal distance between the copies of any two vertices in $G^{\prime}$ is even. First claim is that the number of matchings in $G$ and $G^{\prime\prime}$ are the same. To see this it is enough to show that: $e=(u,v)$ is an edge in $G$ iff any simple path from $u^{\prime}$ to $v^{\prime}$ has odd length. If $e$ is a tree edge then the vertical distance between $u^{\prime}$ and $v^{\prime}$ is $1$ and the horizontal distance is even. Thus the distance between them on the grid is odd and therefore any path between them on the grid has odd length. Similarly, if $e$ is a non-tree edge, then $h(u)$ and $h(v)$ have different parity and therefore the vertical distance between them is odd.

Now we will see how to construct the grid graph $H$ as required by the Lemma. Let $G^{\prime\prime}$ be a $m_{1}\times m_{2}$ grid. Construct an empty grid $H$, of size $(m_{1}+2)\times(m_{2}+2)$. Place the grid $G^{\prime\prime}$ on $H$ so that $G^{\prime\prime}$ lies properly inside the grid (that is no edge of $G^{\prime\prime}$ has an end point on any of the boundary vertices of $H$). Suppose two vertices $u$ and $v$ in $G$ get identified when $G$ is thought of as a genus $g$ graph. Then from our earlier observation we have that both $u^{\prime}$ and $v^{\prime}$ must be leaf nodes and lie on the outer face of $G^{\prime\prime}$. Also $h(u)$ and $h(v)$ must have the same parity, since otherwise we can construct an odd cycle in $G$ by traversing from $s$ to $u$ (which is the same as $v$) and back to $s$ via $v$. This implies that the $y$-coordinate of both $u^{\prime}$ and $v^{\prime}$ in $G^{\prime\prime}$ has the same parity. Drop a path from $u$ (and similarly a path from $v$) by going down all the way to the south border of $H$. Observe that the sum of the lengths of these two paths is even. This is because, the difference in their $y$-coordinates is even. This ensures that matching is preserved by adding these paths.

The ordering of the segments in the outer face that get glued, is same in both $H$ and $G$ since faces are preserved by the reduction in [ABC+09]. Also the by our construction the length of each segment is even since the horizontal distance between two vertices is a multiple of $2$. Additionally from there are no edges along the boundary of the grid as required. ∎

1 Any graph in a“genus g𝑔g grid” is bipartite

Let $C$ be a cycle in $G$. First we consider the case when $C$ is a simple cycle. Partition $C$ into paths $P_{1}=(p_{1},\ldots,p_{2}),P_{2}=(p_{2},\ldots,p_{3}),\ldots,P_{k}=(p_{k},\ldots,p_{1})$, such that each $P_{i}$ lies entirely in the grid with its two end points $p_{i}$ and $p_{i+1}$ lying on some two segments. An example of this partition is shown in Figure 10(a) for the respective cycle. For each path $P_{i}$ construct a path $P^{\prime}_{i}$ by moving along the border of the grid from $p_{i}$ to $p_{i+1}$ along a fixed direction (say in clockwise direction).

Fix an $i\in[k]$. Consider the partition of $P^{\prime}_{i}$, induced by the segments along which it passes. Denote the first and the last partition by $P^{\prime}_{i_{1}}$ and $P^{\prime}_{i_{2}}$ respectively. Note that any of the intermediate partitions of $P^{\prime}_{i}$ has even length since the length of an intermediate partition equals the length of the corresponding segment and hence is even. Therefore we have,

because the path $P_{i}$ and $P^{\prime}_{i}$ together form a simple cycle on the grid and any cycle that lies entirely on the grid has even length. Consider the sum,

Since $|P^{\prime}_{i_{2}}|$ and $|P^{\prime}_{{((i+1)\mod k)}_{1}}|$ are equal, we have,

Now combining Equations (3.1), (3.2) and (3.5), we have $\sum_{i=1}^{k}|P_{i}|$ is even and thus $C$ is of even length.

If $C$ is non-simple, then $C$ can be decomposed into a collection of simple cycles $\{C_{j}\}$ such that $|C|=\sum_{j}C_{j}$. Now using the previous part we get that $C$ has even length. ∎

New Upper Bounds

In this section we establish new upper bounds on the space complexity of certain matching problems on bipartite constant genus graphs, embedded on a ‘genus $g$ grid’.

We define \GG to be the class of genus $g$ graphs such that: for every $G\in\GG$, $G$ is a grid graph embedded on a grid of size $2m\times 2m$. We assume that the distance between adjacent horizontal (and similarly vertical) vertices is of unit length. The entire boundary of the grid is divided into $4g$ segments, and each segment has even length, for some constant $g$. The $4g$ segments are labelled as $(S_{1},S_{2},S_{1}^{\prime},S_{2}^{\prime},\ldots S_{2i-1},S_{2i},S_{2i-1}^{\prime},S_{2i}^{\prime},$ $\ldots,S_{2g-1},S_{2g},S_{2g-1}^{\prime},S_{2g}^{\prime})$, together with a direction, namely, $S_{i}$ is directed from left to right and $S_{i}^{\prime}$ is directed from right to left for each $i\in[2g]$. The $j$th vertex on a segment $S_{i}$ is the $j$th vertex on the border of the grid, starting from the head of the segment $S_{i}$ and going along the direction of the segment. Finally the segments $S_{i}$ and $S_{i}^{\prime}$ are glued to each other for each $i\in[2g]$ in the same direction. In other words, the $j$th vertex on segment $S_{i}$ is the same as the $j$th vertex on segment $S_{i}^{\prime}$. Also there are no edges along the boundary of the grid.

If $C$ is a cycle in $G$, we denote the circulation of $C$ with respect to a weight function $w$ as $circ_{w}(C)$. For any subset $E^{\prime}\subseteq C$, $circ_{w}(E^{\prime})$ is the value of the circulation restricted to the edges of $E^{\prime}$.

There exists a logspace computable and polynomially bounded weight function $W$, such that for any graph $G\in\GG$ and any cycle $C\in G$, $circ_{W}(C)\neq 0$.

For a graph embedded on a constant genus surface,

As a result of Theorem 3, we can assume that our input graph $G\in\GG$. Using Theorem 10 and Lemma 1 we get a logspace computable weight function $W$, such that the minimum weight perfect matching in $G$ with respect to $W$ is unique. Moreover, for any subset $E^{\prime}\subseteq E$, Theorem 10 is valid for the subgraph $G\setminus E^{\prime}$ also, with respect to the same weight function $W$. Now (a) and (b) follows from Lemma 2. Checking for uniqueness can be done by first computing a perfect matching, then deleting an edge from the matching and rechecking to see if a perfect matching exists in the new graph. If it does, then $G$ did not have a unique perfect matching, else it did. Note that Theorem 10 is valid for any graph formed by deletion of edges of $G$. ∎

Theorem 10 also gives an alternative proof of directed graph reachability for constant genus graphs.

Directed graph reachability for constant genus graphs is in \UL.

The proof of Theorem 12 follows from Lemma 13 and [BTV09]. We adapt Lemma 13 from the journal version of [DKR08] (to appear in Theory of Computing Systems).

There exist a logspace computable weight function that assigns polynomially bounded weights to the edges of a directed graph such that: (a) the weights are skew symmetric, i.e., w(u,v) = - w(v,u), and (b) the sum of weights along any (simple) directed cycle is non-zero.

In any class of graphs closed under the subdivision of edges, Theorem 10 implies the hypothesis of Lemma 13.

Given an undirected graph $G,$ construct a bipartite graph $G^{\prime}$ as follows: replace every undirected edge $\{u,v\}$ by a path $u-w-v$ of length two. Use Lemma 13 to assign weights to the edges of $G^{\prime}.$ Suppose that the weight assigned to the undirected edge $\{u,w\}$ in $G^{\prime}$ is $a$ and the weight of $\{w,v\}$ is $b.$ Let $\overrightarrow{G}$ denote the directed graph obtained from $G$ by considering each undirected edge as two directed edges in opposite directions. Now we assign the weights to the edges of $\overrightarrow{G}$ as follows: directed edge $(u,v)$ gets weight $a-b;$ whereas the directed edge $(v,u)$ will get weight $b-a.$ The circulations of the cycles in $G^{\prime}$ being non-zero will translate into the sum of the edges along any cycle in the directed graph $\overrightarrow{G}$ being non-zero. ∎

For a graph $G\in\GG$, we define $W$ is a linear combination of the following $4g+1$ weight functions defined below. This is possible in logspace since $g$ is constant.

Define $4g+1$ weight functions as follows:

Note that if $e$ does not lie on the boundary of the grid then $w^{\prime\prime}(e)$ is same as the weight function defined in [DKR08].

If $C$ is a cycle in $G$, we denote the circulation of $C$ with respect to a weight function $w$ as $circ_{w}(C)$. For any subset $E^{\prime}\subseteq C$, $circ_{w}(E^{\prime})$ is the value of the circulation restricted to the edges of $E^{\prime}$. An example of a cycle on a grid is given in Figure 10(a).

Let $C$ be a simple cycle in $G$. If $C$ is surface non-separating, then $circ_{w_{i}}(C)\neq 0$ for some $i$. If $C$ is surface separating and crosses the boundary of the grid at some vertex $v$, then $circ_{w^{\prime}_{i}}(C)\neq 0$ for $i$, such that $v$ lies in the segment $S_{i}$. If $C$ does not intersect any of the boundary segments, then $C$ does not have any edge on the boundary since there are no edges along the boundary by definition of \GG. Therefore $circ_{w^{\prime\prime}}(C)\neq 0$ by [DKR08].

Without loss of generality, assume $C$ intersects segment $S_{1}$. Let $E^{C}_{1}$ be the set of edges of $C$ that intersect $S_{1}$. Note that $circ_{w_{1}}(C)=circ_{w_{1}}(E^{C}_{1})$ (same thing holds for $w^{\prime}_{1}$ as well. We can assume that $|E^{C}_{1}|$ is even since otherwise $circ_{w_{1}}(E^{C}_{1})$ is odd and hence non-zero. By Lemma 16 it follows that the edges of $E^{C}_{1}$, alternate between going out and coming into the grid. Then using Lemma 17 we get that $circ_{w^{\prime}_{1}}(E^{C}_{1})\neq 0$ and thus $circ_{w^{\prime}_{1}}(C)\neq 0$. (See below for Lemma 16 and 17) ∎

To establish Lemma 16 we use an argument (Lemma 15) from homology theory. For two cycles (directed or undirected) $C_{1}$ and $C_{2}$, let $I(C_{1},C_{2})$ denote the number of times $C_{1}$ and $C_{2}$ cross each other (that is one of them goes from the left to the right side of the other, or vice versa).

Next we adapt the following Lemma from Cabello and Mohar [CM07]. Here we assume we are given an orientable surface (Cabello and Mohar gives a proof for a graph on a surface).

Given a genus $g$ orientable, surface $\Gamma$, let $\mathcal{C}=\{C_{i}\}_{i\in[2g]}$ be a set of cycles that generate the first homology group $H_{1}(\Gamma)$. A cycle $C$ in $\Gamma$ in non-separating if and only if there is some cycle $C_{i}\in\mathcal{C}$ such that $I(C,C_{i})\equiv 1(\mod 2)$.

Suppose $C$ is non-separating. One can construct a cycle $C^{\prime}$ on $\Gamma$, that intersects $C$ exactly once. Let $C^{\prime}=\sum_{i\in[2g]}t_{i}^{\prime}C_{i}$. Now $1\equiv I_{C^{\prime}}(C)\equiv\sum_{i\in[2g]}t_{i}^{\prime}I(C,C_{i})(\mod 2)$. This implies that there exists $i\in[2g]$ such that $I(C,C_{i})\equiv 1(\mod 2)$. ∎

Let $C$ be a simple directed cycle on a genus $g$ orientable surface $\Gamma$ and let $\mathcal{C}=\{C_{i}\}_{i\in[2g]}$ be a system of $2g$ directed cycles on $\Gamma$, having exactly one point in common and $\Gamma\setminus\mathcal{C}$ is the fundamental polygon, say $\Gamma^{\prime}$. If $I(C,C_{i})$ is even for all $i\in[2g]$ then for all $j\in[2g]$, $C$ alternates between going from left to right and from right to left of the cycle $C_{j}$ in the direction of $C_{j}$ (if $C$ crosses $C_{j}$ at all).

Suppose there exists a $j\in[2g]$ such that $C$ does not alternate being going from left to right and from right to left with respect to $C_{j}$. Thus if we consider the ordered set of points where $C$ intersects $C_{j}$, ordered in the direction of $C_{j}$, there are two consecutive points (say $P_{1}$ and $P_{2}$) such that at both these points $C$ crosses $C_{j}$ in the same direction.

Let $Q_{1}$ and $Q_{2}$ be two points in $\Gamma\setminus C$. We will show that there exists a path in $\Gamma\setminus C$ between $Q_{1}$ and $Q_{2}$. Consider the shortest path from $Q_{1}$ to $C$. Let $Q_{1}^{\prime}$ be the point on this path that is as close to $C$ as possible, without lying on $C$. Similarly define a point $Q_{2}^{\prime}$ corresponding to $Q_{2}$. Note that it is sufficient for us to construct a path between $Q_{1}^{\prime}$ and $Q_{2}^{\prime}$ in $\Gamma\setminus C$. If both $Q_{1}^{\prime}$ and $Q_{2}^{\prime}$ locally lie on the same side of $C$, then we get a path from $Q_{1}^{\prime}$ to $Q_{2}^{\prime}$ not intersecting $C$, by traversing along the boundary of $C$. Now suppose $Q_{1}^{\prime}$ and $Q_{2}^{\prime}$ lie on opposite sides (w.l.o.g. assume that $Q_{1}^{\prime}$ lies on the right side) of $C$. From $Q_{1}^{\prime}$ start traversing the cycle until you reach cycle $C_{j}$ (point $P_{1}$ in Figure 10(b)). Continue along cycle $C_{j}$ towards the adjacent intersection point of $C$ and $C_{j}$, going as close to $C$ as possible, without intersecting it (point $P_{2}$ in Figure 10(b)). Essentially this corresponds to switching from one side of $C$ to the other side without intersecting it. Next traverse along $C$ to reach $Q_{2}^{\prime}$. Thus we have a path from $Q_{1}^{\prime}$ to $Q_{2}^{\prime}$ in $\Gamma\setminus C$. We give an example of this traversal in Figure 10(b). This implies that $C$ is non-separating.

It is well known that $\mathcal{C}$ forms a generating set of $H_{1}(\Gamma)$, the first homology group of the surface. Now from Lemma 15 it follows that $I(C,C_{l})\equiv 1(\mod 2)$ for some $l\in[2g]$, which is a contradiction.

Let $G$ be a graph in \GG with $C$ being a simple cycle in $G$ and $E^{C}_{1}$ being the set of edges of $C$ that intersects segment $S_{1}$. Assume $|E^{C}_{1}|$ is even and the edges in $E^{C}_{1}$ alternate between going out and coming into the grid. Let $i_{1}<i_{2}<\ldots<i_{2p-1}<i_{2p}$ be the distinct indices on $S_{1}$ where $C$ intersects it. Then

and thus non-zero unless $E^{C}_{1}$ is empty.

Let $e_{j}=(u_{j},v_{j})$ for $j\in[2p]$ be the $2p$ edges of $G$ lying on the segment $S_{1}$. Assume without loss of generality that the vertices $v_{j}$’s lie on $S_{1}$. Assign an orientation to $C$ such that $e_{1}$ is directed from $u_{1}$ to $v_{1}$. Also assume that $i_{1}$ is even and the circulation gives a positive sign to the edge $e_{1}$. Therefore $circ_{w^{\prime}_{1}}(\{e_{1}\})=-i_{1}$.

Now consider any edge $e_{j}$ such that $j$ is even. By Lemma 16, the edge enters the segment $S_{1}$. Suppose $i_{j}$ is odd. Then consider the following cycle $C^{\prime}$ formed by tracing $C$ from $u_{j}$ to $u_{1}$, without the edges $e_{1}$ and $e_{j}$ and then moving along the segment $S_{1}$ back to $u_{j}$. Since $i_{j}$ is odd therefore the latter part of $C^{\prime}$ has odd length. Note that $C^{\prime}$ need not be a simple cycle. By Lemma 9, $|C^{\prime}|$ is even, therefore the part of $C^{\prime}$ from $u_{1}$ to $u_{j}$ also has odd length. This implies that the circulation gives a positive sign to the edge $e_{j}$. Therefore, $circ_{w^{\prime}_{1}}(\{e_{j}\})=i_{j}$. Similarly, if $i_{j}$ is odd, then the part of $C^{\prime}$ from $u_{1}$ to $u_{j}$ will have even length. Thus the circulation gives a negative sign to the edge $e_{j}$ and therefore $circ_{w^{\prime}_{1}}(\{e_{j}\})=-(-i_{j})=i_{j}$.

If $j$ is odd, the above argument can be applied to show that $circ_{w^{\prime}_{1}}(\{e_{j}\})=-i_{j}$. Therefore we have,

Now removing the assumptions at the beginning of this proof would show that the LHS and RHS of the above equation is true modulo absolute value as required. ∎

It is interesting to note here that similar method does not show that bipartite matching in non-orientable constant genus graphs is in \SPL. The reason is that Lemma 16 crucially uses the fact that the surface is orientable. In fact, one can easily come with counterexample to the Lemma if the surface is non-orientable.

Reducing the non-orientable case to the orientable case

Let $G$ be a bipartite graph embedded on a genus $g$ non-orientable surface. As a result of Theorem 6 we can assume that we are given a combinatorial embedding (say $\Pi$) of $G$ on a (non-orientable) polygonal schema, say $\Lambda(\Gamma),$ in the normal form with $2g^{\prime}$ sides. (Here $g^{\prime}$ is a function of $g.$)

Let $Y=(X_{1},X_{2})$ be the cyclic ordering of the labels of the sides of $\Lambda(\Gamma)$, where $X_{2}$ is the ‘orientable part’ and $X_{1}$ is the ‘non-orientable part’. More precisely, for the polygonal schema in the normal form, we have: $X_{1}$ is either $(\sigma,\sigma)$ (thus corresponds to the projective plane) or it is $(\sigma,\tau,\bar{\sigma},\tau)$ (thus corresponds to the Klein bottle). See Figure 11.

Now let $G$ be a bipartite graph embedded on a non-orientable polygonal schema $\Lambda(\Gamma)$ with $2g^{\prime}$ sides. We will construct a graph $G^{\prime}$ embedded on an orientable polygonal schema with $4g^{\prime}-2$ sides such that $G$ has a perfect matching iff $G^{\prime}$ has a perfect matching. Moreover, given a perfect matching in $G^{\prime}$ one can retrieve in logspace a perfect matching in $G.$ This is illustrated in the following Theorem.

Let $G$ be a bipartite graph given with its embedding on a non-orientable polygonal schema in normal form $\Lambda(\Gamma)$, with $2g^{\prime}$ sides as above. One can construct in logspace, another graph $G^{\prime}$ together with its embedding on the polygonal schema of an orientable surface $\Gamma^{\prime}$ of genus $4g^{\prime}-2$ such that: $G$ has a perfect matching iff $G^{\prime}$ has a perfect matching. Moreover, given a perfect matching in $G^{\prime},$ one can construct in logspace a perfect matching in $G.$

We first show the case when $\Gamma$ is the sum of an orientable surface and a Klein bottle. Consider the polygonal schema formed by taking two copies of $\Lambda(\Gamma)$ and glueing the side $\tau$ of one copy with its partnered side $\tau$ of the other copy. We relabel the edge labelled $\sigma$ in the second copy with some unused symbol $\delta$ to avoid confusion. The entire reduction is shown in Figure 12. Let $G^{\prime}$ be the resulting graph.

Note that the polygonal schema obtained as a result represents an orientable surface and has constantly many sides. Also every vertex and edge in $G$ has exactly two copies in $G^{\prime}$ and $G^{\prime}$ is also bipartite. Let $M$ be a matching in $G$. Let $M^{\prime}$ be the union of the edges of $M$ from both the copies of $G$ . Its easy to see that $M^{\prime}$ is a matching in $G^{\prime}$. Now consider a matching $M^{\prime}$ in $G^{\prime}$. The projection of $M^{\prime}$ to $G$ gives a subgraph of $G$ where every vertex has degree (counted with multiplicity) exactly two. Since $G$ is bipartite, one can obtain a perfect matching within this subgraph.

Now consider the case when $\Gamma$ is the ‘sum’ of an orientable surface and a projective plane, i.e., following the notation above $X_{1}$ corresponds to the labels of a polygonal schema for the projective plane and $X_{2}$ corresponds to the labels of a polygonal schema of an orientable surface. Take two copies of $\Lambda(\Gamma)$, and glue $\sigma$ of one copy with its partner $\sigma$ in the other copy. We show this operation in Figure 13.

The rest of the proof is similar to the Klein bottle case. ∎

Thus we see that the non-orientable case can be reduced to the orientable case. The resulting polygonal schema need not be in the normal form. Once again we apply Theorem 6 to get a combinatorial embedding on a polygonal schema in the normal form.

Acknowledgment

The third author would like to thank Prof. Mark Brittenham from the Mathematics department at the University of Nebraska-Lincoln, for numerous discussions that they had and for providing valuable insight into topics in algebraic topology.

References