Is it NP-hard to decide if an arbitrary bipartite graph has 2 edge disjoint perfect matchings? It is hard for cubic graphs, but I am not sure whether it is still hard for bipartite graphs.
Finding 2 edge disjoint perfect matching in a bipartite graph
bipartite-graphscombinatoricsgraph theorymatching-theorynp-complete
Related Question
- [Math] Number of perfect matchings in a complete bipartite graph with equal partitions
- [Math] Show that a bipartite graph G is a union of ∆(G) matchings (maximum degree)
- Proving a bipartite graph does not have a perfect matching
- Perfect matching preserving connectedness in regular bipartite graph
- Partition the edges of a bipartite graph into perfect $b$-matchings
- Number of perfect matchings in a complete bipartite graph without any edge repetition
Best Answer
This is a 2-matching problem, and so is polynomial. Because the graph is bipartite, a perfect 2-matching consists in a disjoint union of even cycles, and thus can be decomposed into 2 disjoint perfect matchings.
Algorithmically, for $G = (U \cup W, E)$, this can be solved by a single maximum $st$-flow computation, where $s$ and $t$ are new vertices, with new arcs $su$ and $wt$ for all $u \in U$, $w \in W$, with capacities 2, and arcs in $E$ are oriented from $U$ to $W$ and have capacities 1.