Perfect Matching problem is polynomial time solvable in general graphs. Given undirected simple graph,

Is the problem of finding two perfect matching with minimum shared edges between them efficiently solvable?

Shared edge is an edge that occurs in both perfect matchings.


Consider a 3-regular graph $G = (V,E)$.

If there is an edge colouring of $G$ with 3 colours, then you have a partition of $E$ in 3 disjoint perfect matchings. In particular, you can find 2 disjoint perfect matchings.

Conversely, if you can find two disjoint perfect matchings $M_1$ and $M_2$, you can also find a third disjoint perfect matching $M_3 = E \setminus (M_1 \cup M_2)$. The partition $\{M_1, M_2, M_3\}$ of $E$ is an edge colouring of $G$ with 3 colours.

Deciding if a 3-regular graph has an edge colouring with 3 colours is NP-hard (Holyer 1981). Hence it is also NP-hard to decide if there are two disjoint perfect matchings (i.e., to decide if the minimum number of shared edges is 0).

| cite | improve this answer | |
  • $\begingroup$ @Jukka, I'm aware of this result. Can you Cary out the reduction from edge-coloring in general graphs to 2-disjoint perfect matchings? . In general graphs, the chromatic index is greater than $\Delta(G)$. So you must have $k$-perfect matchings. $\endgroup$ – Mohammad Al-Turkistany Sep 14 '10 at 14:55
  • $\begingroup$ The OP asks for 2-Perfect matchings in General graphs with minimum shared edges. $\endgroup$ – Mohammad Al-Turkistany Sep 14 '10 at 15:13
  • 1
    $\begingroup$ If the problem is NP-hard even in the special case of 3-regular graphs, then certainly it can't be easy to solve in general graphs, right? And if it's NP-hard to decide if the optimal solution has 0 shared edges (= disjoint perfect matchings) or > 0 shared edges (= non-disjoint perfect matchings), then the optimisation problem is NP-hard, too? $\endgroup$ – Jukka Suomela Sep 14 '10 at 15:17
  • 1
    $\begingroup$ Are you seriously suggesting that even though your problem is NP-hard for cubic graphs, it might still admit a polynomial-time algorithm in the general case (which of course includes all cubic graphs)? $\endgroup$ – Jukka Suomela Sep 14 '10 at 16:01
  • 1
    $\begingroup$ Of course it is also a reduction from finding a 3-edge-colouring in cubic graphs (an NP-hard problem) to finding 2 disjoint perfect matchings in general graphs, if you prefer to see it like that. Assume that you have a black box $M$ that decides if there are 2 disjoint perfect matchings in a given (general) graph $G$. The above reduction shows that, using $M$, we can solve the following NP-complete problem: decide if a given cubic graph has a 3-edge-colouring. $\endgroup$ – Jukka Suomela Sep 14 '10 at 16:26

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.