It is a well-known result that a bipartite graph can be decomposed into edge-disjoint perfect matchings if and only if it is regular. Now here comes the question. Given a bipartite regular graph, is there a polynomial-time algorithm to find such a decomposition into edge-disjoint perfect matchings? If this bipartite regular graph is also vertex-transitive, is it easier to find such a decomposition?
$\begingroup$
$\endgroup$
7
-
2$\begingroup$ The standard proof of the result already gives a simple polynomial-time algorithm: find a perfect matching, remove it from the graph (which preserves its being regular bipartite), rinse and repeat until the graph is empty. I don’t know if there is anything more efficient. $\endgroup$– Emil JeřábekCommented Aug 10, 2022 at 6:20
-
1$\begingroup$ If the graph is $d$ Regular for $d$ Power of 2, then there is a nice linear time algorithm (O($m$)) time $\endgroup$– AspiringMatCommented Aug 10, 2022 at 6:42
-
2$\begingroup$ Specifically, find an Eulerian cycle and remove m/2 edges from B to A. You get a d/2 regular graph with m/2 edges. Repeat recursively until you have your matching $\endgroup$– AspiringMatCommented Aug 10, 2022 at 6:47
-
$\begingroup$ @AspiringMat Good idea. You can use it even if $d$ is not a power of $2$: if $d$ is even, find an Eulerian cycle as you describe, halving the degree; if $d$ is odd, find and remove a perfect matching first, making $d$ even. Then repeat. $\endgroup$– Emil JeřábekCommented Aug 10, 2022 at 7:56
-
1$\begingroup$ But note that even in the power of 2 case, you need to recursively process both halves of the graph to get a decomposition. Thus, this will be time $O(m\log m)$ rather than $O(m)$. This time bound holds for general $d$ as well (finding perfect matchings in regular bipartite graphs can be done in time $O(m)$). $\endgroup$– Emil JeřábekCommented Aug 10, 2022 at 8:03
|
Show 2 more comments