Complexity results for matching cut problems in graphs without long induced paths
Preprint
Abstract
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), and 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, and (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. 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.
Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- The complexity of the perfect matching‐cut problemJournal of Graph Theory, 2024
- Finding Matching Cuts in H-Free GraphsAlgorithmica, 2023
- Refined notions of parameterized enumeration kernels with applications to matching cut enumerationJournal of Computer and System Sciences, 2022
- Matching Cut in Graphs with Large Minimum DegreeAlgorithmica, 2020
- Algorithms solving the Matching Cut problemTheoretical Computer Science, 2016
- On Promise Problems: A Survey2006
- Which Problems Have Strongly Exponential Complexity?Journal of Computer and System Sciences, 2001
- On the Complexity of k-SATJournal of Computer and System Sciences, 2001
- Matching cutsets in graphsJournal of Graph Theory, 1989
- Recognizing decomposable graphsJournal of Graph Theory, 1984