# #StackBounty: #complexity-theory #graphs #np-complete #np-hard #np Karp hardness of searching for a matching split

### Bounty: 50

This is yet another follow-up question in the series:

Karp hardness of searching for a matching cut

Karp hardness of searching for a matching erosion

In this question, we further restrict the notion of a matching erosion (which is already a restricted notion of a matching cut). Formally, our definition is as follows.

Given an undirected graph \$G(V, E)\$, a matching split \$M=(A, B)\$ is a partition of \$V\$ into two disjoint subsets, i.e. \$Acap B = emptyset land Acup B = V\$ that satisfies the following conditions:

• \$G[A]\$ and \$G[B]\$ are two disjoint induced subgraphs
• The edge set of the cut \$M = {uvin Evert uin A land v in B}\$ is a matching (here, we abuse the notation a little bit, \$M\$ is both the partition \$(A, B)\$ and the edge set of the matching cut)
• Each vertex \$uin A\$ is incident to exactly one edge in \$M\$
• Each vertex \$uin B\$ is incident to exactly one edge in \$M\$

Clearly, we should have \$|A|=|B|=|V|/2\$, hence the name of this concept.

Our decision problem Matching Split naturally asks whether a given graph \$G\$ has a matching split.

Our question is: What is the complexity of deciding Matching Split?

Get this bounty!!!

This site uses Akismet to reduce spam. Learn how your comment data is processed.