2
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Dmitry Kamenetsky Feb 9 at 8:45
  • $\begingroup$ I'm not sure what you mean – you get to choose $b$. $\endgroup$ – Yuval Filmus Feb 9 at 8:51
  • $\begingroup$ 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. $\endgroup$ – Dmitry Kamenetsky Feb 9 at 8:53
  • $\begingroup$ Ah – now I see what you mean. $\endgroup$ – Yuval Filmus Feb 9 at 8:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.