1
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
10
$\begingroup$

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).

Improve this answer
$\endgroup$
9
  • $\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, 2010 at 14:55
  • $\begingroup$ The OP asks for 2-Perfect matchings in General graphs with minimum shared edges. $\endgroup$
    – Mohammad Al-Turkistany
    Sep 14, 2010 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, 2010 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, 2010 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, 2010 at 16:26

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.