Finding Matching Cuts in H-Free Graphs

Lucke, Felicia; Paulusma, Daniël; Ries, Bernard

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 (The complexity of the Perfect Matching-Cut problem. CoRR, arXiv:2011.03318, (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. (2023). Finding Matching Cuts in H-Free Graphs. Algorithmica, 85(10), 3290-3322. https://doi.org/10.1007/s00453-023-01137-9

• Journal Article Type: Article
• Acceptance Date: May 24, 2023
• Online Publication Date: Jun 7, 2023
• Publication Date: 2023-10
• Deposit Date: Aug 10, 2023
• Publicly Available Date: Aug 10, 2023
• Journal: Algorithmica
• Print ISSN: 0178-4617
• Electronic ISSN: 1432-0541
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Volume: 85
• Issue: 10
• Pages: 3290-3322
• DOI: https://doi.org/10.1007/s00453-023-01137-9
• Keywords: Applied Mathematics; Computer Science Applications; General Computer Science
• Public URL: https://durham-repository.worktribe.com/output/1715385