English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The (Perfect) Matching Cut problem is to decide if a graph $G$ has a(perfect) matching cut, i.e., a (perfect) matching that is also an edge cut of$G$. Both Matching Cut and Perfect Matching Cut are known to be NP-complete. Aperfect matching cut is also a matching cut with maximum number of edges. Toincrease our understanding of the relationship between the two problems, weintroduce the Maximum Matching Cut problem. This problem is to determine alargest matching cut in a graph. We generalize and unify known polynomial-timealgorithms for Matching Cut and Perfect Matching Cut restricted to graphs ofdiameter at most $2$ and to $(P_6+sP_2)$-free graphs. We also show that thecomplexity of Maximum Matching Cut differs from the complexities of MatchingCut and Perfect Matching Cut by proving NP-hardness of Maximum Matching Cut for$2P_3$-free quadrangulated graphs of diameter $3$ and radius $2$ and forsubcubic line graphs of triangle-free graphs. In this way, we obtain fulldichotomies of Maximum Matching Cut for graphs of bounded diameter, boundedradius and $H$-free graphs. Finally, we apply our techniques to get a dichotomyfor the Maximum Disconnected Perfect Matching problem for $H$-free graphs. Adisconnected perfect matching of a graph $G$ is a perfect matching thatcontains a matching cut of $G$. The Maximum Disconnected Perfect Matchingproblem asks to determine for a connected graph $G$, a disconnected perfectmatching with a largest matching cut over all disconnected perfect matchings of$G$. Our dichotomy result implies that the original decision problemDisconnected Perfect Matching is polynomial-time solvable for $(P_6+sP_2)$-freegraphs for every $s\geq 0$, which resolves an open problem of Bouquet andPicouleau (arXiv, 2020).

Dichotomies for Maximum Matching Cut: $H$-Freeness, Bounded Diameter, Bounded Radius