# Find a minimum-weight perfect b-matching, where b is even

How would one find a minimum-weight perfect b-matching of a general graph, where the number of edges incident on each vertex is a positive even number not greater than b?

A minimum-weight perfect b-matching of a graph G is a subgraph M of minimal total edge weight, such that each vertex in G is incident by exactly b edges from M.

• What is a perfect $b$-matching? Please make your question self-contained. – Yuval Filmus Feb 9 '19 at 6:38
• added definition of a perfect b-matching. Note that I actually want a perfect b-matching where b is also even and positive. – Dmitry Kamenetsky Feb 9 '19 at 6:41

## 1 Answer

A subgraph in which each vertex has degree exactly $$b$$ is known as a $$b$$-factor. You are asking for something similar (but not identical) to the minimum weight $$b$$-factor.

Tutte showed how to reduce minimum weight $$b$$-factor to minimum weight perfect matching in his paper A short proof of the factor theorem for finite graphs.

We will split each vertex $$v$$ of degree $$d(v)$$ into $$2d(v) - b$$ vertices: $$v_1,\ldots,v_{d(v)},v'_1,\ldots,v'_{d(v)-b}$$ (we can assume that $$d(v) \geq b$$, since otherwise the graph has no $$b$$-factor). We lift each edge $$(x,y)$$ to an edge $$(x_i,y_j)$$ of the same weight in such a way that each $$x_i$$ and $$y_j$$ participates in exactly one such edge. We furthermore connect each $$v_i$$ to each $$v'_j$$ with a zero-weight edge, for all $$i \in [d(v)]$$ and $$j \in [d(v)-b]$$.

Each $$b$$-factor of the original graph corresponds to a matching in the new graph of the same weight. Indeed, lift the $$b$$-factor to the new graph, and for each vertex $$v$$, add an arbitrary matching between $$v'_1,\ldots,v'_{d(v)-b}$$ and the $$d(v)-b$$ new vertices corresponding to "unused ports".

Conversely, we can convert every matching in the new graph to a $$b$$-factor of the same weight in the original graph by undoing this construction.

• Thank you! This is exactly the algorithm I had in mind. It’s amazing that Tutte found it so long ago. I also wanted to force b to be even and positive. For this to work we can create 4d(v)-b vertices with 2d(v)-b of them ports. We also need to connect pairs of ports together. – Dmitry Kamenetsky Feb 9 '19 at 8:45
• I'm not sure what you mean – you get to choose $b$. – Yuval Filmus Feb 9 '19 at 8:51
• So you choose an even b. Now I want every vertex to be incident by an even number of edges in the matching less or equal to b. If b is 6 then the allowed number of incident edges is 2, 4 or 6. 5 edges would not be allowed. – Dmitry Kamenetsky Feb 9 '19 at 8:53
• Ah – now I see what you mean. – Yuval Filmus Feb 9 '19 at 8:54