Cyclewidth and the Grid Theorem for Perfect Matching Width of Bipartite Graphs

Abstract

A connected graph G is called matching covered if every edge of G is contained in a perfect matching. Perfect matching width is a width parameter for matching covered graphs based on a branch decomposition. It was introduced by Norine and intended as a tool for the structural study of matching covered graphs, especially in the context of Pfaffian orientations. Norine conjectured that graphs of high perfect matching width contain a large grid as a matching minor, similar to the result on treewidth by Robertson and Seymour.

In this paper we obtain the first results on perfect matching width since its introduction. For the restricted case of bipartite graphs, we show that perfect matching width is equivalent to directed treewidth and thus, the Directed Grid Theorem by Kawarabayashi and Kreutzer for directed treewidth implies Norine’s conjecture.

This work has been supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (ERC consolidator grant DISTRUCT, agreement No. 648527).

1 Introduction

The concept of width parameters, or decompositions of graphs into tree-like structures has proven to be a powerful tool in both structural graph theory and for coping with computational intractability. The shining star among these concepts is the treewidth of undirected graphs introduced in its popular form in the Graph Minor series by Robertson and Seymour (see [RS10]).

Tree decompositions are a way to decompose a given graph into loosely connected small subgraphs of bounded size that, in many algorithmic applications, can be dealt with individually instead of considering the graph as a whole. This concept allows the use of dynamic programming and other techniques to solve many hard computational problems (see for example [Bod96, Bod97, Bod05, DF16]). A major milestone in the graph minor project was the Grid Theorem [RS86], which states that if the treewidth of a graph is sufficiently high, the graph has a large grid as a minor.

A natural generalisation of treewidth to directed graphs, directed treewidth, was introduced by Reed in [Ree99] and by Johnson et al. in [JRST01] along with the conjecture of a directed version of the Grid Theorem. After being open for several years, the conjecture was proven by Kawarabayashi and Kreutzer [KK15]).

It is possible to go further and to consider even more general structures than directed graphs. One of the ways to do this is to characterise (strongly connected) directed graphs by pairs of undirected bipartite graphs and perfect matchings. The generalisation (up to the strong connectivity) is then to drop the condition on the graphs to be bipartite. The theory of matching minors in matching covered graphs is deeply connected to the theory of butterfly minors in strongly connected directed graphs. This connection can be used to show structural results on directed graphs by using matching theory (see [McC00, GT11]).

The corresponding branch of graph theory was developed from the theory of tight cuts and tight cut decompositions of matching covered graphs introduced by Kotzig, Lovász and Plummer [Lov87, LP09, Kot60]. A graph is matching covered if it is connected and each of its edges is contained in a perfect matching. One of the main incentives of the field is the question of Pfaffian orientations; see [McC04, Tho06] for an overview on the subject. Matching minors can be used to characterise the bipartite Pfaffian graphs [McC04, RST99]. The characterisation implies a polynomial time algorithm for the problem to decide whether a matching covered bipartite graph is Pfaffian or not.

While no polynomial time algorithm for recognising general Pfaffian graphs is known, Norine defines a branch decomposition for matching covered graphs and gives an algorithm that decides whether a graph from a class of bounded perfect matching width is Pfaffian in XP-time. Norine and Thomas also conjecture a grid theorem for this new width parameter (see [Nor05, Tho06]). Based on the above mentioned ties between bipartite matching covered graphs and directed graphs, Norine conjectures in his thesis that the Grid Theorem for digraphs would at least imply the conjecture in the bipartite case. Whether perfect matching width and directed treewidth could be seen as equivalent was unknown at that time.

Contribution. We prove that high perfect matching width of a bipartite graph implies that it has a large cylindrical grid as a matching minor, which settles the Matching Grid Conjecture for the bipartite case. We also show that the reverse direction holds. To do so, in Sect. 2, we introduce a branch decomposition and a corresponding new width parameter for directed graphs, cyclewidth, and prove its equivalence to directed treewidth. This new width measure is very interesting in itself and not only because, while equivalent to treewidth, it is much better behaved since it is closed under minors.

As an advantage of cyclewidth we consider that its introduction leads to a straightforward proof of the Matching Grid Theorem for bipartite graphs: in Sect. 3 we show that cyclewidth and perfect matching width are within a constant factor of each other; this immediately implies the Matching Grid Theorem for bipartite graphs. Our proofs are algorithmic and thus also imply an approximation algorithm for perfect matching width on bipartite graphs, which is the first known result on this matter.

We also show that the perfect matching width of a matching minor of a matching covered bipartite graph is at most two times higher than the perfect matching width of the original graph.

A width parameter like cyclewidth never considers an edge that is not contained in a directed cycle. So, when studying cyclewidth and related topics, one might restrict themselves to strongly connected digraphs. Similarly, an edge that is not contained in any perfect matching is, in most cases, irrelevant for the matching theoretic properties of the graph. For this reason it is common to only consider matching covered graphs as this does not pose any loss of generality.

We take the freedom to rename Norine’s matching-width [Nor05] to perfect matching width to better distinguish it from related parameters such as maximum matching width (see [JST17]).

1.1 Preliminaries

We consider finite graphs and digraphs without multiple edges and use standard notation (see [Die17]). For a graph G, its vertex set is denoted by V(G) and its edge set by E(G), and similarly for digraphs where we call arcs edges.

Let $X \subseteq V(G)$ be a non-empty set of vertices in a graph G. The cut around X is the set $\mathchoice{\partial \,\!\left( X \right) }{\partial \,\!\left( X \right) }{\partial \left( X \right) }{\partial \left( X \right) }\subseteq E(G)$ of all edges joining vertices of X to vertices of $V(G) \setminus X$. We call X and $V(G) \setminus X$ the shores of $\mathchoice{\partial \,\!\left( X \right) }{\partial \,\!\left( X \right) }{\partial \left( X \right) }{\partial \left( X \right) }$. A set $E\subseteq E(G)$ is a cut if $E = \mathchoice{\partial \,\!\left( X \right) }{\partial \,\!\left( X \right) }{\partial \left( X \right) }{\partial \left( X \right) }$ for some X. Note that in connected graphs the shores are uniquely defined.

A matching of a graph G is a set $M \subseteq E(G)$ such that no two edges in M share a common endpoint. If $e=xy\in M$, e is said to cover the two vertices x and y. A matching M is called perfect if every vertex of G is covered by an edge of M. We denote by $\mathchoice{\mathcal {M}\,\!\left( G \right) }{\mathcal {M}\,\!\left( G \right) }{\mathcal {M}\left( G \right) }{\mathcal {M}\left( G \right) }$ the set of all perfect matchings of a graph G. A graph G is called matching covered if G is connected and for every edge $e \in E(G)$ there is an $M \in \mathchoice{\mathcal {M}\,\!\left( G \right) }{\mathcal {M}\,\!\left( G \right) }{\mathcal {M}\left( G \right) }{\mathcal {M}\left( G \right) }$ with $e \in M$.

Definition 1.1

Let $G=\left( A\cup B, E \right)$ be a bipartite graph and let $M\in \mathchoice{\mathcal {M}\,\!\left( G \right) }{\mathcal {M}\,\!\left( G \right) }{\mathcal {M}\left( G \right) }{\mathcal {M}\left( G \right) }$ be a perfect matching of G. The M-direction $\mathchoice{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\left( G,M \right) }{\mathcal {D}\left( G,M \right) }$ of G is defined as follows (see also Fig. 1). Let $M = \left\{ a_1b_1,\dots ,a_{\left| M \right| }b_{\left| M \right| } \right\}$ with $a_i\in A, b_i\in B$ for $1\le i\le \left| M \right|$. Then,

• (i) and

• (ii) .

Thus, the M-direction $\mathchoice{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\left( G,M \right) }{\mathcal {D}\left( G,M \right) }$ of G is defined by contracting the edges of M, and orienting the remaining edges of G from A to B. The following is a well known observation about M-directions.

Fig. 1.

A bipartite graph $G=\left( A\cup B,E \right)$ with perfect matching and its -direction.

Lemma 1.2

A digraph D is strongly connected if and only if there is a bipartite matching covered graph G and a perfect matching $M\in \mathchoice{\mathcal {M}\,\!\left( G \right) }{\mathcal {M}\,\!\left( G \right) }{\mathcal {M}\left( G \right) }{\mathcal {M}\left( G \right) }$ such that D is isomorphic to $\mathchoice{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\left( G,M \right) }{\mathcal {D}\left( G,M \right) }$. Furthermore, the pair (G, M) is uniquely defined by D.

This shows why matching covered graphs are such a meaningful graph class, because they correspond to the strongly connected directed graphs.

2 Directed Treewidth and Cyclewidth

Since perfect matching width is defined via a branch decomposition, our first step towards showing the asymptotic equivalence of directed treewidth and perfect matching width of bipartite graphs is to relate directed treewidth to cyclewidth, a directed branchwidth parameter. In Sect. 2.1, we introduce cyclewidth and show that it provides a linear lower bound on the directed treewidth. Then, in Sect. 2.2, we show that taking butterfly minors does not increase the cyclewidth and that large cylindrical grids have large cyclewidth. The Directed Grid Theorem then implies that there exists a function that bounds the cyclewidth of a digraph from below by its directed treewidth.

2.1 Cyclewidth: A Branch Decomposition for Digraphs

An arborescence is a directed tree T with a root $r_0$ and all edges directed away from $r_0$. Let D be a digraph and let $Z\subseteq V(D)$. A set $S\subseteq V(D)-Z$ is Z-normal if there is no directed walk in $D-Z$ with the first and last vertex in S that uses a vertex of $D-\left( Z\cup S \right)$.

Definition 2.1

A directed tree decomposition of a digraph D is given by a triple $\left( T,\beta ,\gamma \right)$, where T is an arborescence, $\beta :V(T)\rightarrow 2^{V\left( D \right) }$ and $\gamma :E(T)\rightarrow 2^{V\left( D \right) }$ are functions such that

• (i) $\left\{ \beta (t) \mid t\in V(T) \right\}$ is a partition of V(D) into possibly empty sets, and

• (ii) if $e\in E(T)$, then $\bigcup \left\{ \beta (t) \mid t\in V(T),t>e \right\}$ is $\gamma (e)$-normal.

For any $t\in V(T)$ we define , where $e\sim t$ means that e is incident with t. The width of $\left( T,\delta ,\gamma \right)$ is the least integer w such that $\left| \varGamma (t) \right| \le w+1$ for all $t\in V(T)$. The directed treewidth $\mathsf {dtw}(D)$ of D is the least integer w such that D has a directed tree decomposition of width w. The sets $\beta (t)$ are called bags and the sets $\gamma (e)$ are called the guards of the directed tree decomposition. For a subtree $T'$ of T we write $\beta (T')$ for $\bigcup _{v \in V(T)} \beta (v)$.

Definition 2.2

(Butterfly Minor). Let D be a digraph. An edge $e=\left( u,v \right) \in E(D)$ is butterfly-contractible if e is the only outgoing edge of u or the only incoming edge of v. A butterfly contraction is the operation of identifying the endpoints of a butterfly-contractible edge and deleting any resulting multiple edges and loops. A digraph $D'$ is a butterfly-minor of D, if it can be obtained from a subgraph of D by butterfly contractions.

Definition 2.3

(Cylindrical Grid). A cylindrical grid ${\text {D}}^{\circlearrowright }_{k}$ of order k consists of k concentric directed cycles and 2k paths connecting the cycles in alternating directions, see Fig. 2.

Fig. 2.

A cylindrical grid of order 6.

Theorem 2.4

(Kawarabayashi and Kreutzer [KK15]). There is a function such that every digraph D either satisfies $\mathsf {dtw}(D)\le \ k$, or contains the cylindrical grid of order f(k) as a butterfly minor.

The problem of relating directed treewidth and perfect matching width is that the latter is defined by a branch decomposition where the value of a cut is determined locally with respect to the cut while, in a directed tree decomposition, the guards of a tree edge may appear almost everywhere in the graph.

In order to approach this problem, we introduce a new width parameter, which is defined over a branch decomposition.

Let T be a tree and $e = tt' \in E(T)$. Then where $T_1$ is the subtree containing t and $T_2$ the subtrees containing $t'$ in $T-e$. Let $\mathchoice{L\,\!\left( T \right) }{L\,\!\left( T \right) }{L\left( T \right) }{L\left( T \right) }$ denote the set of leaves of T.

Definition 2.5

(Cyclewidth). Let D be a digraph. A cycle decomposition of D is a tuple $\left( T,\varphi \right)$, where T is a cubic tree (i.e. all inner vertices have degree three) and $\varphi :\mathchoice{L\,\!\left( T \right) }{L\,\!\left( T \right) }{L\left( T \right) }{L\left( T \right) } \rightarrow V(D)$ is a bijection. For a subtree $T'$ of T we use . Let $t_1t_2 \in E(T)$ and let . Let . The cyclic porosity of the edge $t_1t_2$ is defined as

The width of a cycle decomposition $\left( T,\varphi \right)$ is given by and the cyclewidth of D is defined as

The factor of might seem arbitrary and it kind of is. We added it because otherwise cyclewidth would only take even numbers which is a quite strange property for a width measure.

In order to show that directed treewidth bounds cyclewidth from above by a function, we construct a cycle decomposition from a directed tree decomposition in two steps. First, we push all vertices contained in bags of inner vertices of the arborescence into leaf bags. Second, we transform the result into a cubic tree.

Lemma 2.6

Let $\left( T,\beta ,\gamma \right)$ be a directed tree decomposition of a digraph D. There is a linear time algorithm that computes a directed tree decomposition $\left( T',\beta ',\gamma ' \right)$ of D of the same width such that $\left| \beta '(\ell ) \right| =1$ for all $\ell \in \mathchoice{L\,\!\left( T' \right) }{L\,\!\left( T' \right) }{L\left( T' \right) }{L\left( T' \right) }$ and $\beta '(t) =\emptyset$ for all inner vertices of T.

Proof

(sketch). For every $t\in V(T) \setminus L(T)$ we introduce a new child $t'$ with and where $st \in E(T)$. Finally, . It is easy to confirm that the construction yields a directed tree decomposition of the same width as $\left( T,\beta ,\gamma \right)$.    $\square$

We call a directed tree decomposition like the one we obtain from Lemma 2.6 a leaf directed tree decomposition. For the second step we need to further manipulate this decomposition. A cycle decomposition requires a cubic tree, therefore we have to transform the arborescence of our decomposition into one of total degree 3 at every vertex. To achieve this we replace every high degree vertex by a long path and attach the children one at a time while maintaining the guards. Then, for every vertex of degree two we contract one of its incident edges.

Lemma 2.7

If the directed treewidth of a digraph D is at most k, then there is a cubic leaf directed tree decomposition of width k for D.

Both constructions in the proofs of Lemmata 2.6 and 2.7 can be computed in linear time. It remains to observe that if we forget the orientation of the edges as well as the guard function of the resulting decomposition, we obtain a cycle decomposition of bounded width.

Proposition 2.8

For every digraph D holds $\mathchoice{\mathsf {cw}\,\!\left( D \right) }{\mathsf {cw}\,\!\left( D \right) }{\mathsf {cw}\left( D \right) }{\mathsf {cw}\left( D \right) } \le \mathsf {dtw}(D)$. Moreover, a cycle decomposition of D of width at most k can be computed from a directed tree decomposition of D of width k.

This can be done in polynomial time.

2.2 Cyclewidth and Cylindrical Grids

The goal of this subsection is to establish a lower bound on the cyclewidth of a digraph in terms of its directed treewidth. Here we face a special challenge. Most width parameters, including directed treewidth, imply separations of bounded size, namely in the width of the decomposition. For cyclewidth it is not immediately clear whether there exists a function such that, given a digraph D and a cut $\mathchoice{\partial \,\!\left( X \right) }{\partial \,\!\left( X \right) }{\partial \left( X \right) }{\partial \left( X \right) }$ in D, there always is a set $S\subseteq V(D)$ that hits all directed cycles crossing $\mathchoice{\partial \,\!\left( X \right) }{\partial \,\!\left( X \right) }{\partial \left( X \right) }{\partial \left( X \right) }$ and satisfying $\left| S \right| \le f(\mathchoice{{\text {cp}}\,\!\left( \mathchoice{\partial \,\!\left( X \right) }{\partial \,\!\left( X \right) }{\partial \left( X \right) }{\partial \left( X \right) } \right) }{{\text {cp}}\,\!\left( \mathchoice{\partial \,\!\left( X \right) }{\partial \,\!\left( X \right) }{\partial \left( X \right) }{\partial \left( X \right) } \right) }{{\text {cp}}\left( \mathchoice{\partial \,\!\left( X \right) }{\partial \,\!\left( X \right) }{\partial \left( X \right) }{\partial \left( X \right) } \right) }{{\text {cp}}\left( \mathchoice{\partial \,\!\left( X \right) }{\partial \,\!\left( X \right) }{\partial \left( X \right) }{\partial \left( X \right) } \right) })$.

We take a different approach. We show that the cyclewidth of cylindrical grids is unbounded and that cyclewidth is closed under taking butterfly minors (a property that does not hold for directed treewidth as shown by Adler [Adl07]). The Directed Grid Theorem then implies the desired result.

Theorem 2.9

If D is a digraph and $D'$ is a butterfly minor of D, then $\mathchoice{\mathsf {cw}\,\!\left( D' \right) }{\mathsf {cw}\,\!\left( D' \right) }{\mathsf {cw}\left( D' \right) }{\mathsf {cw}\left( D' \right) } \le \mathchoice{\mathsf {cw}\,\!\left( D \right) }{\mathsf {cw}\,\!\left( D \right) }{\mathsf {cw}\left( D \right) }{\mathsf {cw}\left( D \right) }$.

For some intuition behind Theorem 2.9 note that, if an edge e is butterfly contractible, every directed cycle containing one of the two endpoints of e must contain e itself. Therefore, by contracting the edge no new cycles are generated and so if there is a family of directed cycles in $D'$ that witnesses the cycle porosity of some cut in $D'$, it corresponds to a family of cycles in D witnessing the cycle porosity of the corresponding cut. This property is especially interesting, because directed treewidth itself is not closed under butterfly minors.

Lemma 2.10

The cylindrical grid of order k has cyclewidth at least .

Proof

(sketch). Every cycle decomposition of every digraph D contains an edge e that induces a bipartition of V(D) where both partitions contain at least a third of V(D). For a cycle decomposition of a large cylindrical grid, consider such an edge. In case that both shores contain a concentric cycle $C_1$ and $C_2$ of the grid, the cycle starting at $C_1$, going to $C_2$, returning to $C_1$ and so on intersects the cut with every change between $C_1$ and $C_2$. In the other case one of the shores contains no concentric cycle completely. The other shore can contain at most two third of the concentric cycles completely, i.e. the remaining (at least k/3) cycles cross the cut.    $\square$

We conclude this section by stating and proving its main result: the equivalence between directed treewidth and cyclewidth.

Theorem 2.11

A class $\mathcal {D}$ of digraphs is a class of bounded directed treewidth if and only if it is a class of bounded cyclewidth.

Proof

Let $\mathcal {D}$ be a class of digraphs. Suppose $\mathcal {D}$ has unbounded directed treewidth, then for each there is a digraph $D'_n\in \mathcal {D}$ such that $\mathsf {dtw}(D')\ge n$. By Theorem 2.4, we can conclude that for every there is a digraph $D_n\in \mathcal {D}$ that contains the cylindrical grid of order n as a butterfly minor. Therefore, $\mathchoice{\mathsf {cw}\,\!\left( D_n \right) }{\mathsf {cw}\,\!\left( D_n \right) }{\mathsf {cw}\left( D_n \right) }{\mathsf {cw}\left( D_n \right) } \ge \frac{n}{3}$ by Lemma 2.10 and Theorem 2.9. Thus, $\mathcal {D}$ has also unbounded cyclewidth. Vice versa, assume $\mathcal {D}$ is of bounded directed treewidth. Then it also is of bounded cyclewidth due to Proposition 2.8.    $\square$

3 Perfect Matching Width

We now leave the world of directed graphs and start to consider undirected graphs with perfect matchings. As seen in Lemma 1.2, strongly connected directed graphs correspond to matching covered bipartite graphs with a fixed perfect matching. We discuss this correspondence in more detail in this section. The goal of this section is to establish a connection between the perfect matching width of bipartite matching covered graphs and the directed treewidth of their M-directions.

A set $S \subseteq V(G)$ of vertices is called conformal if $G-S$ has a perfect matching. Given a perfect matching $M \in \mathchoice{\mathcal {M}\,\!\left( G \right) }{\mathcal {M}\,\!\left( G \right) }{\mathcal {M}\left( G \right) }{\mathcal {M}\left( G \right) }$, a set $S\subseteq V(G)$ is called M-conformal if M contains a perfect matching of both $G-S$ and $G[S]$. A subgraph $H\subseteq G$ is conformal if V(H) is a conformal set and it is called M-conformal if V(H) is M-conformal. If a cycle C is M-conformal, there is another perfect matching $M'\ne M$ with $E(C) \setminus M \subseteq M'$. Hence, if needed, we say C is M-$M'$-conformal to indicate that M and $M'$ form a partition of the edges of C.

3.1 Perfect Matching Width and Directed Cycles

Definition 3.1

(Perfect Matching Width). Let G be a matching covered graph. We define the matching-porosity of $\mathchoice{\partial \,\!\left( X \right) }{\partial \,\!\left( X \right) }{\partial \left( X \right) }{\partial \left( X \right) }$ as follows:

A perfect matching decomposition of G is a tuple $\left( T,\delta \right)$ where T is a cubic tree and $\delta :\mathchoice{L\,\!\left( T \right) }{L\,\!\left( T \right) }{L\left( T \right) }{L\left( T \right) } \rightarrow V(G)$ a bijection. Let e be an edge in T. Removing the edge e splits T in two subtrees $T_1$ and $T_2$. Let

be the two classes of that partition. Note that $\mathchoice{\partial \,\!\left( X_1 \right) }{\partial \,\!\left( X_1 \right) }{\partial \left( X_1 \right) }{\partial \left( X_1 \right) } = \mathchoice{\partial \,\!\left( X_2 \right) }{\partial \,\!\left( X_2 \right) }{\partial \left( X_2 \right) }{\partial \left( X_2 \right) }$ defines an edge cut in G, we refer to it by $\mathchoice{\partial \,\!\left( e \right) }{\partial \,\!\left( e \right) }{\partial \left( e \right) }{\partial \left( e \right) }$. The width of $\left( T,\delta \right)$ is given by $\max _{e \in E(T)} \mathchoice{{\text {mp}}\,\!\left( e \right) }{{\text {mp}}\,\!\left( e \right) }{{\text {mp}}\left( e \right) }{{\text {mp}}\left( e \right) }$ and the perfect matching width of G is then defined as

If we consider the M-direction of a matching covered bipartite graph G with $M\in \mathchoice{\mathcal {M}\,\!\left( G \right) }{\mathcal {M}\,\!\left( G \right) }{\mathcal {M}\left( G \right) }{\mathcal {M}\left( G \right) }$, then any cycle decomposition $\left( T,\varphi \right)$ of $\mathchoice{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\left( G,M \right) }{\mathcal {D}\left( G,M \right) }$ can be interpreted as a decomposition of G where $\varphi$ is a bijection between $\mathchoice{L\,\!\left( T \right) }{L\,\!\left( T \right) }{L\left( T \right) }{L\left( T \right) }$ and M. Then, every edge in T induces a bipartition of V(G) into M-conformal sets. The next definition relates this observation to perfect matching decompositions.

Definition 3.2

(M-Perfect Matching Width). Let G be a matching covered graph and $M \in \mathchoice{\mathcal {M}\,\!\left( G \right) }{\mathcal {M}\,\!\left( G \right) }{\mathcal {M}\left( G \right) }{\mathcal {M}\left( G \right) }$. Define S as the set of all perfect matching decompositions $\left( T,\delta \right)$ of G such that for every inner edge e holds if $\left( T_1,T_2 \right) = T\ltimes e$, then $\delta (\mathchoice{L\,\!\left( T_1 \right) }{L\,\!\left( T_1 \right) }{L\left( T_1 \right) }{L\left( T_1 \right) })$ and $\delta (\mathchoice{L\,\!\left( T_2 \right) }{L\,\!\left( T_2 \right) }{L\left( T_2 \right) }{L\left( T_2 \right) })$ are M-conformal. The M-perfect matching width, $M\text {-}\mathsf {pmw}$, is defined as

Here again the factor avoids the measure to take only even numbers.

Proposition 3.3

Let G be a matching covered graph and $M \in \mathchoice{\mathcal {M}\,\!\left( G \right) }{\mathcal {M}\,\!\left( G \right) }{\mathcal {M}\left( G \right) }{\mathcal {M}\left( G \right) }$. Then, .

Proof

(sketch). The first inequality is trivial. For the second one consider a cut $\mathchoice{\partial \,\!\left( X \right) }{\partial \,\!\left( X \right) }{\partial \left( X \right) }{\partial \left( X \right) }$ of matching porosity k. Then, our desired perfect matching M has at most k edges in $\mathchoice{\partial \,\!\left( X \right) }{\partial \,\!\left( X \right) }{\partial \left( X \right) }{\partial \left( X \right) }$. Therefore, we have to shift at most k vertices from X to $\overline{X}$ in order to obtain a cut between two M-conformal sets. Since we shift at most k vertices for every cut, the matching porosity increases by at most k, so it ends up to be 2k. Thus the M-perfect matching width is k again.    $\square$

We now need the following observation. Let $G=\left( A\cup B,E \right)$ be a bipartite matching covered graph and $M,M'\in \mathchoice{\mathcal {M}\,\!\left( G \right) }{\mathcal {M}\,\!\left( G \right) }{\mathcal {M}\left( G \right) }{\mathcal {M}\left( G \right) }$ two distinct perfect matchings. Then the graph induced by $M\cup M'$ consists only of isolated edges and M-$M'$-conformal cycles. Moreover, the isolated edges are exactly the set $M\cap M'$. Let C be such an M-$M'$-conformal cycle. Then in both, $\mathchoice{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\left( G,M \right) }{\mathcal {D}\left( G,M \right) }$ and $\mathchoice{\mathcal {D}\,\!\left( G,M' \right) }{\mathcal {D}\,\!\left( G,M' \right) }{\mathcal {D}\left( G,M' \right) }{\mathcal {D}\left( G,M' \right) }$, C corresponds to a directed cycle. On the other hand let $N\in \mathchoice{\mathcal {M}\,\!\left( G \right) }{\mathcal {M}\,\!\left( G \right) }{\mathcal {M}\left( G \right) }{\mathcal {M}\left( G \right) }$ and let C be a directed cycle in $\mathchoice{\mathcal {D}\,\!\left( G,N \right) }{\mathcal {D}\,\!\left( G,N \right) }{\mathcal {D}\left( G,N \right) }{\mathcal {D}\left( G,N \right) }$. Then C corresponds to an N-conformal cycle $C_N$ in G of exactly double the length, where E(C) and $E(C_N) \setminus N$ coincide (if we forget the direction of edges in C). Thus $\left( N\setminus E(C_N) \right) \cup \left( E(C_N) \setminus N \right)$ is a perfect matching of G.

So there is a one-to-one correspondence between the directed cycles in $\mathchoice{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\left( G,M \right) }{\mathcal {D}\left( G,M \right) }$ and the M-conformal cycles in G. Using this insight we can translate an M-perfect matching decomposition of G to a cycle decomposition of $\mathchoice{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\left( G,M \right) }{\mathcal {D}\left( G,M \right) }$ and back, which yields the next lemma.

Lemma 3.4

Let G be a bipartite and matching covered graph and $M \in \mathchoice{\mathcal {M}\,\!\left( G \right) }{\mathcal {M}\,\!\left( G \right) }{\mathcal {M}\left( G \right) }{\mathcal {M}\left( G \right) }$. Then $M\text {-}\mathchoice{\mathsf {pmw}\,\!\left( G \right) }{\mathsf {pmw}\,\!\left( G \right) }{\mathsf {pmw}\left( G \right) }{\mathsf {pmw}\left( G \right) } = \mathchoice{\mathsf {cw}\,\!\left( \mathchoice{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\left( G,M \right) }{\mathcal {D}\left( G,M \right) } \right) }{\mathsf {cw}\,\!\left( \mathchoice{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\left( G,M \right) }{\mathcal {D}\left( G,M \right) } \right) }{\mathsf {cw}\left( \mathchoice{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\left( G,M \right) }{\mathcal {D}\left( G,M \right) } \right) }{\mathsf {cw}\left( \mathchoice{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\left( G,M \right) }{\mathcal {D}\left( G,M \right) } \right) }$.

The following theorem is an immediate corollary of Proposition 3.3 and Lemma 3.4.

Theorem 3.5

Let G be a bipartite and matching covered graph and $M \in \mathchoice{\mathcal {M}\,\!\left( G \right) }{\mathcal {M}\,\!\left( G \right) }{\mathcal {M}\left( G \right) }{\mathcal {M}\left( G \right) }$. Then .

3.2 The Bipartite Matching Grid

We now almost have all pieces in place to deduce the grid theorem for matching covered bipartite graphs. The only missing piece is a minor concept for matching covered graphs. The standard concept of contractions in graphs reduces the number of vertices by exactly one. Thus, it does not preserve the property whether the graph contains a perfect matching. However, if we always consider conformal subgraphs and contract two edges at a time, parity is not an issue.

The idea of matching minors appears in the work of McGuaig [McC01], but the formal framework and the actual name were introduced by Norine and Thomas in [NT07].

Definition 3.6

(Bicontraction). Let G be a graph and let $v_0$ be a vertex of G of degree two incident to the edges $e_1=v_0v_1$ and $e_2=v_0v_2$. Let H be obtained from G by contracting both $e_1$ and $e_2$ and deleting all resulting parallel edges. We say H is obtained from G by bicontraction or bicontracting the vertex $v_0$.

Definition 3.7

(Matching Minor). Let G and H be graphs. We say that H is a matching minor of G if H can be obtained from a conformal subgraph of G by repeatedly bicontracting vertices of degree two.

There is a strong relation between matching minors of bipartite matching covered graphs and butterfly minors of strongly connected digraphs.

Lemma 3.8

(McGuaig [McC00]). Let G and H be bipartite matching covered graphs. Then H is a matching minor of G if and only if there exist perfect matchings $M\in \mathchoice{\mathcal {M}\,\!\left( G \right) }{\mathcal {M}\,\!\left( G \right) }{\mathcal {M}\left( G \right) }{\mathcal {M}\left( G \right) }$ and $M'\in \mathchoice{\mathcal {M}\,\!\left( H \right) }{\mathcal {M}\,\!\left( H \right) }{\mathcal {M}\left( H \right) }{\mathcal {M}\left( H \right) }$ such that $\mathchoice{\mathcal {D}\,\!\left( H,M' \right) }{\mathcal {D}\,\!\left( H,M' \right) }{\mathcal {D}\left( H,M' \right) }{\mathcal {D}\left( H,M' \right) }$ is a butterfly minor of $\mathchoice{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\left( G,M \right) }{\mathcal {D}\left( G,M \right) }$.

We want to establish a relation between the perfect matching width of a matching covered graph and the perfect matching width of its matching minors. By using our result on the relation of the cyclewidth of digraphs and the cyclewidth of their butterfly minors, we are able to derive the next result.

Proposition 3.9

Let G and H be matching covered bipartite graphs. If H is a matching minor of G, then $\mathchoice{\mathsf {pmw}\,\!\left( H \right) }{\mathsf {pmw}\,\!\left( H \right) }{\mathsf {pmw}\left( H \right) }{\mathsf {pmw}\left( H \right) } \le 2\mathchoice{\mathsf {pmw}\,\!\left( G \right) }{\mathsf {pmw}\,\!\left( G \right) }{\mathsf {pmw}\left( G \right) }{\mathsf {pmw}\left( G \right) }$.

Proof

Let H be a matching minor of G. Then, Lemma 3.8 provides the existence of perfect matchings $M\in \mathchoice{\mathcal {M}\,\!\left( G \right) }{\mathcal {M}\,\!\left( G \right) }{\mathcal {M}\left( G \right) }{\mathcal {M}\left( G \right) }$ and $M'\in \mathchoice{\mathcal {M}\,\!\left( H \right) }{\mathcal {M}\,\!\left( H \right) }{\mathcal {M}\left( H \right) }{\mathcal {M}\left( H \right) }$ such that $\mathchoice{\mathcal {D}\,\!\left( H,M' \right) }{\mathcal {D}\,\!\left( H,M' \right) }{\mathcal {D}\left( H,M' \right) }{\mathcal {D}\left( H,M' \right) }$ is a butterfly minor of $\mathchoice{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\left( G,M \right) }{\mathcal {D}\left( G,M \right) }$. The M-perfect matching width of G is at most $\mathchoice{\mathsf {pmw}\,\!\left( G \right) }{\mathsf {pmw}\,\!\left( G \right) }{\mathsf {pmw}\left( G \right) }{\mathsf {pmw}\left( G \right) }$ by Proposition 3.3 and, by Lemma 3.4, $M\text {-}\mathchoice{\mathsf {pmw}\,\!\left( G \right) }{\mathsf {pmw}\,\!\left( G \right) }{\mathsf {pmw}\left( G \right) }{\mathsf {pmw}\left( G \right) } =\mathchoice{\mathsf {cw}\,\!\left( \mathchoice{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\left( G,M \right) }{\mathcal {D}\left( G,M \right) } \right) }{\mathsf {cw}\,\!\left( \mathchoice{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\left( G,M \right) }{\mathcal {D}\left( G,M \right) } \right) }{\mathsf {cw}\left( \mathchoice{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\left( G,M \right) }{\mathcal {D}\left( G,M \right) } \right) }{\mathsf {cw}\left( \mathchoice{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\left( G,M \right) }{\mathcal {D}\left( G,M \right) } \right) }$. Since $\mathchoice{\mathcal {D}\,\!\left( H,M' \right) }{\mathcal {D}\,\!\left( H,M' \right) }{\mathcal {D}\left( H,M' \right) }{\mathcal {D}\left( H,M' \right) }$ is a butterfly minor of $\mathchoice{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\left( G,M \right) }{\mathcal {D}\left( G,M \right) }$, Theorem 2.9 gives us $\mathchoice{\mathsf {cw}\,\!\left( \mathchoice{\mathcal {D}\,\!\left( H,M' \right) }{\mathcal {D}\,\!\left( H,M' \right) }{\mathcal {D}\left( H,M' \right) }{\mathcal {D}\left( H,M' \right) } \right) }{\mathsf {cw}\,\!\left( \mathchoice{\mathcal {D}\,\!\left( H,M' \right) }{\mathcal {D}\,\!\left( H,M' \right) }{\mathcal {D}\left( H,M' \right) }{\mathcal {D}\left( H,M' \right) } \right) }{\mathsf {cw}\left( \mathchoice{\mathcal {D}\,\!\left( H,M' \right) }{\mathcal {D}\,\!\left( H,M' \right) }{\mathcal {D}\left( H,M' \right) }{\mathcal {D}\left( H,M' \right) } \right) }{\mathsf {cw}\left( \mathchoice{\mathcal {D}\,\!\left( H,M' \right) }{\mathcal {D}\,\!\left( H,M' \right) }{\mathcal {D}\left( H,M' \right) }{\mathcal {D}\left( H,M' \right) } \right) } \le \mathchoice{\mathsf {cw}\,\!\left( \mathchoice{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\left( G,M \right) }{\mathcal {D}\left( G,M \right) } \right) }{\mathsf {cw}\,\!\left( \mathchoice{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\left( G,M \right) }{\mathcal {D}\left( G,M \right) } \right) }{\mathsf {cw}\left( \mathchoice{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\left( G,M \right) }{\mathcal {D}\left( G,M \right) } \right) }{\mathsf {cw}\left( \mathchoice{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\,\!\left( G,M \right) }{\mathcal {D}\left( G,M \right) }{\mathcal {D}\left( G,M \right) } \right) }$. At last, using Lemma 3.4 again and combining the above inequalities, we obtain $\mathchoice{\mathsf {pmw}\,\!\left( H \right) }{\mathsf {pmw}\,\!\left( H \right) }{\mathsf {pmw}\left( H \right) }{\mathsf {pmw}\left( H \right) } \le 2\mathchoice{\mathsf {pmw}\,\!\left( G \right) }{\mathsf {pmw}\,\!\left( G \right) }{\mathsf {pmw}\left( G \right) }{\mathsf {pmw}\left( G \right) }$.    $\square$

As we are going for a cylindrical grid and derive the grid theorem for bipartite matching covered graphs from the Directed Grid Theorem anyway, it makes sense to derive our grid from the directed case as well. The following definition defines the bipartite matching grid by providing a procedure that allows us to obtain it from the directed cylindrical grid. Let $E_o$ be the set of edges of the outermost cycle containing exactly those edges which are the sole outgoing edges of their tails. Let $E_i$ be the set of edges of the innermost cycle containing exactly those edges which are the sole incoming edges of their heads.

Definition 3.10

(Bipartite Matching Grid). Let be a positive integer. Let be the digraph obtained from by butterfly contracting every edge from $E_o$ and every edge from $E_i$. The bipartite matching grid of order k is the unique bipartite matching covered graph that has a perfect matching such that .

The uniqueness of and M follows from Lemma 1.2. Figure 3 provides an example. Note that all contractible edges are contained in the innermost and in the outermost cycle of and provide a perfect matching of those two cycles. Here, we construct from . The contractible edges are highlighted.

Fig. 3.

The construction of the bipartite matching grid of order 3 from the (directed) cylindrical grid of order 3

Assume that a bipartite matching covered graph G has high perfect matching width. By Theorem 3.5, this implies high cyclewidth for all M-directions of G. This, in turn, implies large cylindrical grids as butterfly minors on those M-directions. Now Lemma 3.8 allows us to translate these cylindrical grids into matching minors of G and as the perfect matching width of G is bounded from below by the width of its matching minors (Proposition 3.9), we obtain the grid theorem for bipartite matching covered graphs.

Proposition 3.11

There is a function such that every matching covered bipartite graph G either satisfies $\mathchoice{\mathsf {pmw}\,\!\left( G \right) }{\mathsf {pmw}\,\!\left( G \right) }{\mathsf {pmw}\left( G \right) }{\mathsf {pmw}\left( G \right) } \le k$, or contains the bipartite matching grid of order f(k) as a matching minor.

4 Conclusion

We provide a first proof for the bipartite version of the Matching Grid Conjecture. However, this proof relies heavily on machinery found and used in directed graph structure theory and it would be nice to have a completely matching theoretical proof. Moreover, there is probably no hope to extend the methods used for proving the Directed Grid Theorem to the non-bipartite matching covered case which remains open. Most likely, we need a completely novel approach in order to attempt solving this second and much more difficult part of the conjecture.

A smaller and probably more accessible problem occurring in this paper is the question for a nice lower bound on the cyclewidth in terms of directed treewidth. The current proof uses the Directed Grid Theorem and therefore the lower bound is equally exponential as the function provided by the theorem. We conjecture that cyclewidth and directed treewidth are actually within a constant factor of each other, a result that would, most likely, enable us to prove Erdős-Pósa-type results for matching covered bipartite graphs.