11
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Another way of stating this problem would be to ask whether the given graph has a perfect matching which is also a cut. $\endgroup$
    – Mikhail Rudoy
    Commented May 4, 2019 at 7:30

1 Answer 1

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.