4
$\begingroup$

Follow-up question in the series:

Karp hardness of searching for a matching erosion

Karp hardness of searching for a matching split

Maximum Matching Cut problem

Input: An undirected graph $G(V, E)$ and an integer $k$

Output: YES if there exists $M \subseteq E$ such that $M$ is a matching of size $k$ (i.e. $k$ edges) and also a cut, NO otherwise

What is the complexity of this problem? (Turing completeness was established, what can we tell about its Karp hardness?)


An edge cut is a subset of $E$ the removal of which would increase the number of connected component of $G$, and for each edge in the set, its two endpoints are in (two) different components.

$\endgroup$
2
$\begingroup$

You can reduce the problem without cardinality constraint to the problem with cardinality constraint.

For an instance $G=(V,E)$ of the problem without cardinality constraint, simply add $m>|V|/2$ isolated edges as well as $2m$ new vertices. Now there is a matching cut in the old graph if and only if there is a matching cut of size $m+1$ in the new graph.


Edit: One can also add an edge $(u,v)$ for each newly added edge $(u,x)$ and a fixed vertex $v$ in the previous graph to make $G$ connected. The conclusion is the same.

$\endgroup$
  • $\begingroup$ Well, accept for the inspiration this answer made. Really thanks a lot. $\endgroup$ – Thinh D. Nguyen Sep 16 '18 at 4:43
  • $\begingroup$ @ThinhD.Nguyen Added the reduction for connected graph. $\endgroup$ – xskxzr Sep 17 '18 at 3:35
  • $\begingroup$ On the second thought, reducing like this is dangerous. Every $(u, x)$ and $(u, v)$ is now bridge. And a bridge is a clear and sharp matching cut in the literature sense. So your constructed graph always has a matching cut (so many bridges to count for). $\endgroup$ – Thinh D. Nguyen Sep 17 '18 at 3:48
  • $\begingroup$ @ThinhD.Nguyen Yes, but your question asks for whether there is a matching cut of size $k$. $\endgroup$ – xskxzr Sep 17 '18 at 3:50
  • $\begingroup$ So, the crucial difficulty is a matching cut that results in exactly $2$ components. Connectedness can be easily adapted. $\endgroup$ – Thinh D. Nguyen Sep 17 '18 at 3:53
1
$\begingroup$

This is not supposed to be an answer (eventually, being satisfied enough with the literature and my own's new result, I accept this). But, I wanna mention a very closely related result. Namely, without the requirement of cardinality $k$, the problem is NP-complete.

However, using their result, it is immediately that our problem is Turing-complete for $\mathrm{NP}$. The poly-time Turing reduction just query our problem (as an oracle) of every possible $k$.

The Maurizio duo of Roma Tre showed our problem (without the cardinality requirement) to be $\mathrm{NP}$-complete in the paper titled "The Complexity of the Matching-Cut Problem" (pdf file)

What makes their hardness proof not guarantees the cardinality requirement $k$ is that the cardinality of the matching cut inside each clause-gadget (the A, B, C, D, E, F cut types in Table 1 in the paper) can have cardinality of $4$ or $6$. So, we cannot include any cardinality indication $k$ to the produced instance.


UPDATE: There is also literature proof that Maurizio duo's hardness can be proven even when restricted to bipartite graphs of bounded diameter. Though, it is unclear how bipartiteness can help in our problem. Link to the latest article on this topic: https://arxiv.org/pdf/1804.11102.pdf


UPDATE: xskxzr's answer finally settle down Karp hardness for this problem. Strictly speaking, literature notion of a matching cut requires that the given graph to be connected and the resulted graph to be split into exactly $2$ connected components. If more than two components are allowed. Then, based on the idea of xskxzr, I have managed to extend the construction of Maurizio duo of Roma Tre. Just extend the False chain and True chain to the left (or right, it does not matter) but the new vertices only have single edges link (not doubly linked) and each pair (one in the true chain, one in the false chain) is connected by $3$ edges with $2$ new nodes in between. Then, we can extend these two chains to a long enough length, to safely produce a required cardinality $K$. Since to separate the two chains, we can cut through the "middle" edges and finally when "nearly" reaching $K$, cut $2$ edges that link to the further new vertices. It seems to be difficult to reduce under the requirement of connectedness and a clean cut (exactly into $2$ components).

$\endgroup$
  • 1
    $\begingroup$ Maybe this would be better as an edit to the question rather than an answer, so your question is treated by the site as unanswered (which might help it get more attention)? $\endgroup$ – D.W. Sep 8 '18 at 18:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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