Complexity Results for Matching Cut Problems in Graphs Without Long Induced Paths

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 the problem of deciding whether a given graph has a matching cut, respectively, a perfect matching cut. The disconnected perfect matching problem (dpm) is to decide if a graph has a perfect matching that contains a matching cut. Solving an open problem recently posed in [Lucke, Paulusma, Ries (ISAAC 2022) & Feghali, Lucke, Paulusma, Ries (arXiv:2212.12317)], we show that pmc is NP-complete in graphs without induced 14-vertex path P-14. Our reduction also works simultaneously for mc and dpm, improving the previous hardness results of mc on P-19-free graphs and of dpm on P-23-free graphs to P-14-free graphs for both problems. Actually, we prove a slightly stronger result: within P-14-free graphs, it is hard to distinguish between (i) those without matching cuts and those in which every matching cut is a perfect matching cut; (ii) those without perfect matching cuts and those in which every matching cut is a perfect matching cut; (iii) those without disconnected perfect matchings and those in which every matching cut is a perfect matching cut. Moreover, assuming the Exponential Time Hypothesis, none of these problems can be solved in time 2(o(n)) for n-vertex P-14-free input graphs. As a corollary from (i), computing a matching cut with a maximum number of edges is hard, even when restricted to P-14-free graphs. This answers a question asked in [Lucke, Paulusma & Ries (arXiv:2207.07095)]. We also consider the problems in graphs without long induced cycles. It is known that mc is polynomially solvable in graphs without induced cycles of length at least 5 [Moshi (JGT 1989)]. We point out that the same holds for dpm.