#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!!!

Leave a Reply

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