<p>As Mikhail noted, the problem was called Perfect Matching Cut in literatures. It was proved to be NP-complete in the following paper (see Theorem 1 on page 5), with a reduction from monotone 1-in-3-SAT:</p>

<p><a href="https://pdfs.semanticscholar.org/d44c/a18638eadeeb17b69f657cfa06c313646b8c.pdf" rel="noreferrer">Pinar Heggernes, Jan Arne Telle. Partitioning Graphs Into Generalized Dominating Sets.</a></p>

CC BY-SA 4.0
2019-05-04T20:25:00.327Z
2019-05-04T20:25:00.327Z
Wei Zhan
<p>Two-colorable perfect matching problem is to decide whether a graph has coloring with two colors such that each node has exactly one neighbor the same color as itself. The problem was proven to be NP-complete by <a href="http://aleteya.cs.buap.mx/~jlavalle/papers/complexity/p216-schaefer.pdf" rel="noreferrer">Schaefer</a>. It remains NP-complete even for planar cubic graphs.</p>

<p>I am interested in a variant where we want to decide whether input graph has coloring with two colors such each node has exactly one neighbor colored differently from itself. I call this Red-Blue perfect matching problem. I don't know whether this is a known problem.</p>

<blockquote>
  <p>How hard is deciding the existence of Red-Blue perfect matching?</p>
</blockquote>

CC BY-SA 4.0
2019-05-04T07:30:59.770Z
Another way of stating this problem would be to ask whether the given graph has a perfect matching which is also a cut.
Mikhail Rudoy
<cc.complexity-theory><np-hardness>
How hard is deciding the existence of Red-Blue perfect matching?
Mohammad Al-Turkistany
# How hard is deciding the existence of Red-Blue perfect matching?

(Asked by: username_0 on 2019-05-01)

Two-colorable perfect matching problem is to decide whether a graph has coloring with two colors such that each node has exactly one neighbor the same color as itself. The problem was proven to be NP-complete by [Schaefer](http://aleteya.cs.buap.mx/~jlavalle/papers/complexity/p216-schaefer.pdf). It remains NP-complete even for planar cubic graphs.

I am interested in a variant where we want to decide whether input graph has coloring with two colors such each node has exactly one neighbor colored differently from itself. I call this Red-Blue perfect matching problem. I don't know whether this is a known problem.

> How hard is deciding the existence of Red-Blue perfect matching?

**Tags:** cc.complexity-theory, np-hardness

> **Comments:**
> **username_1**: Another way of stating this problem would be to ask whether the given graph has a perfect matching which is also a cut.  

---

## 1 answers

### Answer by username_2 on 2019-05-04. Score: 9 | Accepted answer

As Mikhail noted, the problem was called Perfect Matching Cut in literatures. It was proved to be NP-complete in the following paper (see Theorem 1 on page 5), with a reduction from monotone 1-in-3-SAT:

[Pinar Heggernes, Jan Arne Telle. Partitioning Graphs Into Generalized Dominating Sets.](https://pdfs.semanticscholar.org/d44c/a18638eadeeb17b69f657cfa06c313646b8c.pdf)


---

