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/

Zendy Plus

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

Zendy Tools

Zendy Open

In a graph, a (perfect) matching cut is an edge cut that is a (perfect)matching. Matching Cut (MC), respectively, Perfect Matching Cut (PMC), is theproblem of deciding whether a given graph has a matching cut, respectively, aperfect matching cut. The Disconnected Perfect Matching problem (DPM) is todecide if a graph has a perfect matching that contains a matching cut. Solvingan open problem posed in [Lucke, Paulusma, Ries (ISAAC 2022, Algorithmica 2023)& Feghali, Lucke, Paulusma, Ries (arXiv:2212.12317)], we show that PMC isNP-complete in graphs without induced $14$-vertex path $P_{14}$. Our reductionalso works simultaneously for MC and DPM, improving the previous hardnessresults of MC on $P_{15}$-free graphs and of DPM on $P_{19}$-free graphs to$P_{14}$-free graphs for both problems. Actually, we prove a slightly strongerresult: within $P_{14}$-free $8$-chordal graphs (graphs without chordlesscycles of length at least $9$), it is hard to distinguish between those withoutmatching cuts (respectively, perfect matching cuts, disconnected perfectmatchings) and those in which every matching cut is a perfect matching cut.Moreover, assuming the Exponential Time Hypothesis, none of these problems canbe solved in $2^{o(n)}$ time for $n$-vertex $P_{14}$-free $8$-chordal graphs.On the positive side, we show that, as for MC [Moshi (JGT 1989)], DPM and PMCare polynomially solvable when restricted to $4$-chordal graphs. Together withthe negative results, this partly answers an open question on the complexity ofPMC in $k$-chordal graphs asked in [Le, Telle (TCS 2022) & Lucke, Paulusma,Ries (MFCS 2023)].

Complexity and algorithms for matching cut problems in graphs without long induced paths and cycles