Search

Matching minors are a specialisation of minors fit for the study of graph with perfect matchings. The notion of matching minors has been used to give a structural description of bipartite graphs on which the number of perfect matchings can becomputed efficiently, based on a result of Little, by McCuaig et al. in 1999.In this paper we generalise basic ideas from the graph minor series by Robertson and Seymour to the setting of bipartite graphs with perfect matchings. We introducea version of Erdos-Posa property for matching minors and find a direct link between this property and planarity. From this, it follows that a class of bipartite graphs withperfect matchings has bounded perfect matching width if and only if it excludes aplanar matching minor. We also present algorithms for bipartite graphs of bounded perfect matching width for a matching version of the disjoint paths problem, matching minor containment, and for counting the number of perfect matchings. From our structural results, we obtain that recognising whether a bipartite graphGcontains afixed planar graphHas a matching minor, and that counting the number of perfect matchings of a bipartite graph that excludes a fixed planar graph as a matching minor are both polynomial time solvable.

A bipartite graph B is called a brace if it is connected and every matching of size at most two in B is contained in some perfect matching of B and a cycle C in B is called conformal if B-V(C) has a perfect matching. We show that there do not exist two disjoint alternating paths that form a cross over a conformal cycle C in a brace B if and only if one can reduce B, by an application of a matching theoretic analogue of small clique sums, to a planar brace H in which C bounds a face. We then utilise this result and provide a polynomial time algorithm which solves the 2-linkage problem for alternating paths in bipartite graphs with perfect matchings.

We characterise digraphs of directed treewidth one in terms of forbidden butterfly minors. Moreover, we show that there is a linear relation between the hypertree-width of the dual of the cycle hypergraph of D, i. e. the hypergraph with vertices V (D) where every hyperedge corresponds to a directed cycle in D, and the directed treewidth of D. Based on this we show that a digraph has directed treewidth one if and only if its cycle hypergraph is a hypertree.

The perfect matching polytope, i.e. the convex hull of (incidence vectors of) perfect matchings of a graph is used in many combinatorial algorithms. Kotzig, Lov\'asz and Plummer developed a decomposition theory for graphs with perfect matchings and their corresponding polytopes known as the tight cut decomposition which breaks down every graph into a number of indecomposable graphs, so called bricks. For many properties that are of interest on graphs with perfect matchings, including the description of the perfect matching polytope, it suffices to consider these bricks. A key result by Lov\'asz on the tight cut decomposition is that the list of bricks obtained is the same independent of the choice of tight cuts made during the tight cut decomposition procedure. This implies that finding a tight cut decomposition is polynomial time equivalent to finding a single tight cut. We generalise the notions of a tight cut, a tight cut contraction and a tight cut decomposition to hypergraphs. By providing an example, we show that the outcome of the tight cut decomposition on general hypergraphs is no longer unique. However, we are able to prove that the uniqueness of the tight cut decomposition is preserved on a slight generalisation of uniform hypergraphs. Moreover, we show how the tight cut decomposition leads to a decomposition of the perfect matching polytope of uniformable hypergraphs and that the recognition problem for tight cuts in uniformable hypergraphs is polynomial time solvable.