Complexity and algorithms for matching cut problems in graphs without long induced paths and cycles
| Autor: | Le, Hoang-Oanh, Le, Van Bang |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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 posed in [Lucke, Paulusma, Ries (ISAAC 2022, Algorithmica 2023) & 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_{15}$-free graphs and of DPM on $P_{19}$-free graphs to $P_{14}$-free graphs for both problems. Actually, we prove a slightly stronger result: within $P_{14}$-free $8$-chordal graphs (graphs without chordless cycles of length at least $9$), it is hard to distinguish between those without matching cuts (respectively, perfect matching cuts, 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 $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 PMC are polynomially solvable when restricted to $4$-chordal graphs. Together with the negative results, this partly answers an open question on the complexity of PMC in $k$-chordal graphs asked in [Le, Telle (TCS 2022) & Lucke, Paulusma, Ries (MFCS 2023)]. Comment: Extended version of a WG 2023 paper |
| Databáze: | arXiv |
| Externí odkaz: |
|