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$
2
  • $\begingroup$ What is a perfect $b$-matching? Please make your question self-contained. $\endgroup$ Feb 9, 2019 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$ Feb 9, 2019 at 6:41

1 Answer 1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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