Problems and algorithms requiring non-bipartite matching

Question

While the importance of the non-bipartite matching problem itself from an algorithmic and complexity point of view is well known, applications of non-bipartite matching are hard to find.

I did an online search for hints, but almost always the articles I found lacked problems that demonstrated the need for non-bipartite matching. The few exceptions I found were:

• A scheduling problem [Fujii, Kasami & Ninomiya, 1969] described in Gerard's matching survey

• The oil well drilling problem of [Devine 1973] described in Gerard's matching survey

• The Christofides heuristic for the TSP [Christofides 1976] Wikipedia

• Plotting street maps with minimum pen lifting [Iri&Taguchi 1980] described in Gerard's matching survey

• Kekule structures in chemistry described here

• Nonparametric Tests for Homogeneity [Rosenbaum 2005] described here (Wayback Machine)

• TSP: unraveling of tours with a high number of pairs of crossing edges: Generate a graph $\Gamma$ in which the edges correspond to pairs of crossing tour edges and their weight equals the amount by which the tour length decreases when replacing the respective tour edges by a pair of non-crossing ones.
  The maximum weight matching in $\Gamma$ identifies the pairs of tour-edges whose exchanging incurs the maximal length reduction. That matching may have to be applied several times until all crossings have been removed.

• Optimizing Triangulations: take as nodes the triangles and as edges the sides that are shared by two triangles; in that settig a plethora of cost functions can be envisaged for different optimality criteria. There are two basic operations that can be performed on triangulations, namely

  • diagonal-swapping for the purpose of improving a triangulation:
    • minimum weight matching with length reduction incurred by swapping diagonals as edge cost when striving for minimum weight triangulations
    • maximum weight matching with the increment of the geometric angle between edge-adjacent triangles when striving for "smooth" triangulations like e.g. of terrain data
    • maximum weight matching with the most acute geometric angle of a triangle as edge cost when striving for triangulations of e.g. terrain data, that are in the spirit of planar Delaunay triangulations.
  • merging edge-adjacent triangles for the purpose of generating a quadrilateralization:
    • a minimum weight matching with the circumference of the generated quadrilateral as edge-cost when striving for "fine grained" quadrilateralizations
    • a maximum weight matching over the most acute geometric angle of a generated quadrilateral when striving for the most orthogonal quadrilateralization e.g. for use as finite elements or, as patches for spline interpolation of 3D data.
    • a minimum weight matching with the spatial distance between a quadrilateral's diagonals when striving for quadrilateralizations with planar cells.

Question
are there further applications for non-bipartite matching, especially newer, examples of different areas of applicability?

Answer 1

The dimer model is a statistical mechanics model which uses perfect matchings. A nice introduction to the dimer model is Richard Kenyon's Lectures on Dimers. However, these lecture notes focus on the bipartite case. One very nice result is Kastelyn’s Formula which is Theorem 2 of Section 3 in the lecture notes. For the general (non-bipartite) version of Kastelyn’s Formula see Rich Schwartz's notes. I find these sources easier to follow since they are written by mathematicians, but since you are interested in applications you may also be interested in sources written by physicists. Keywords combinations like "dimer model non-bipartite" and "dimer model triangular lattice" will bring up some relevant (and recent) results. I am also seeing papers on the "quantum dimer model." I am not familiar with this, but it might fit the bill for more recent applications.

One of the more famous examples of using non-bipartite dimers is this article by Fisher which applies dimers to the Ising model. It is from the 1960s, so is not new, but it is a different application. However, here is a more recent paper on arxiv revisiting Fisher's work.

Answer 2

See "Optimal Nonbipartite Matching and Its Statistical Applications" by Lu et al. in The American Statistician Feb 2011.

Answer 3

Let $G$ be a graph and let $\partial : \mathbb F_2^{E(G)} \to \mathbb F_2^{V(G)}$ be the boundary map on edges, extended $\mathbb F_2$-linearly. Then $\ker \partial \leq \mathbb F_2^{E(G)}$ is an error correcting code, and at low error rates the maximum likelihood decoder can be approximated by finding, given an even-sized set of vertices, a set of paths with shortest total length connecting them in pairs. This can be expressed as a minimum weight perfect matching problem on an auxiliary graph.

Whether this is any use of course depends on $G$. Quantum error correction with the surface code is built over some reasonable cellulation of some reasonable 2D surface. Information is stored in the 1D homology group and its dual, so there are two decoding problems, in which $G$ is either the edge set of the cellulation or the edge set of the dual cellulation. Minimum weight perfect matching remains a standard technique for decoding these codes, but there are questions about whether implementations can be fast enough to keep up with quantum hardware.