Finding matching cuts in H-free graphs

Lucke, F.; Paulusma, D.; Ries, B.

Abstract

The well-known NP-complete problem Matching Cut is to decide if a graph has a matching that is also an edge cut of the graph. We prove new complexity results for Matching Cut restricted to H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. We also prove new complexity results for two recently studied variants of Matching Cut, on H-free graphs. The first variant requires that the matching cut must be extendable to a perfect matching of the graph. The second variant requires the matching cut to be a perfect matching. In particular, we prove that there exists a small constant r > 0 such that the first variant is NP-complete for Pr-free graphs. This addresses a question of Bouquet and Picouleau (arXiv, 2020). For all three problems, we give state-of-the-art summaries of their computational complexity for H-free graphs.

Citation

Lucke, F., Paulusma, D., & Ries, B. (2021, December). Finding matching cuts in H-free graphs. Presented at 33rd International Symposium on Algorithms and Computation (ISAAC 2022), Seoul, South Korea

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
• Start Date: Dec 19, 2021
• End Date: Dec 21, 2021
• Acceptance Date: Sep 22, 2022
• Online Publication Date: Dec 14, 2022
• Publication Date: 2022
• Deposit Date: Oct 16, 2022
• Publicly Available Date: Oct 17, 2022
• Pages: 22:1-22:16
• Series Title: LIPIcs
• Series Number: 248
• Book Title: 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
• DOI: https://doi.org/10.4230/lipics.isaac.2022.22
• Public URL: https://durham-repository.worktribe.com/output/1620330
• Related Public URLs: https://arxiv.org/abs/2207.07095