<p>Consider a 3-regular graph $G = (V,E)$.</p>

<p>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.</p>

<p>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.</p>

<p>Deciding if a 3-regular graph has an edge colouring with 3 colours is NP-hard (<a href="http://dx.doi.org/10.1137%2F0210055" rel="noreferrer">Holyer 1981</a>). 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).</p>

CC BY-SA 2.5
2010-09-14T14:55:28.337Z
@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.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-14T15:13:17.153Z
The OP asks for 2-Perfect matchings in General graphs with minimum shared edges.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-14T15:17:43.377Z
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?
Jukka Suomela
CC BY-SA 2.5
2010-09-14T15:38:42.093Z
@Jukka, Is there an obvious reduction from k-disjoint PM to 2-disjoint PM in general graphs? I don't see it. May be removing the regularity restriction make the problem easy.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-14T16:01:03.090Z
@Jukka, Existence of 2-PM in general graphs does not imply the existence of $\Delta$-perfect matchings.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-14T16:01:43.637Z
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)?
Jukka Suomela
CC BY-SA 2.5
2010-09-14T16:26:38.880Z
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.
Jukka Suomela
CC BY-SA 2.5
2010-09-14T16:27:06.773Z
No, your reduction hings on finding 2-PM in CUBIC graphs. So, if you remove this regularity condition, Can you still carry out the reduction?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-14T17:28:40.757Z
@Jukka, I got your oracle argument. Can you help me understand why there is no simple reduction from disjoint $\Delta$-Perfect Matchings in general graphs to disjoint 2-PM in general graphs?.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-14T09:29:54.690Z
2010-09-14T09:29:54.690Z
Jukka Suomela
<p>Perfect Matching problem is polynomial time solvable in general graphs.
Given undirected simple graph, </p>

<blockquote>
  <p>Is the problem of finding two perfect matching with minimum shared edges between them efficiently solvable?</p>
</blockquote>

<p>Shared edge is an edge that occurs in both perfect matchings.</p>

<cc.complexity-theory><matching>
Complexity of two perfect matchings with minimum shared edges?
Mohammad Al-Turkistany
# Complexity of two perfect matchings with minimum shared edges?

(Asked by: username_0 on 2010-09-14)

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.

**Tags:** cc.complexity-theory, matching

---

## 1 answers

### Answer by username_1 on 2010-09-14. Score: 10 | Accepted answer

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](http://dx.doi.org/10.1137%2F0210055)). 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).

> **Comments:**
> **username_0**: @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.  
> **username_0**: The OP asks for 2-Perfect matchings in General graphs with minimum shared edges.  
> **username_1**: 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?  
> **username_0**: @Jukka, Is there an obvious reduction from k-disjoint PM to 2-disjoint PM in general graphs? I don't see it. May be removing the regularity restriction make the problem easy.  
> **username_0**: @Jukka, Existence of 2-PM in general graphs does not imply the existence of $\Delta$-perfect matchings.  
> **username_1**: 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)?  
> **username_1**: 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.  
> **username_0**: No, your reduction hings on finding 2-PM in CUBIC graphs. So, if you remove this regularity condition, Can you still carry out the reduction?  
> **username_0**: @Jukka, I got your oracle argument. Can you help me understand why there is no simple reduction from disjoint $\Delta$-Perfect Matchings in general graphs to disjoint 2-PM in general graphs?.  

---

