Finding matching cuts in H-free graphs

DOI10.1007/S00453-023-01137-9MaRDI QIDQ6046951zbMATH OpenOpenAlexFDO

Authors Felicia Lucke, Daniël Paulusma, Bernard Ries

Publication date 6 October 2023

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2207.07095

zbMATH Keywords

computational complexityperfect matching\(H\)-free graphmatching cut

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Abstract: The 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 $P_r$-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.

Recommendations

• On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs
• MaxCut in ${\bm H)$-Free Graphs
• Matching cutsets in graphs
• A note on matching-cut in \(P_t\)-free graphs
• Maximum cuts in \(\mathscr{H} \)-free graphs
• New results for MaxCut in H$H$‐free graphs
• Matchings in graphs with a given number of cuts
• Matching cut in graphs with large minimum degree
• Matching cut in graphs with large minimum degree
• On the complexity of matching cut in graphs of fixed diameter

Cites work

• scientific article; zbMATH DE number 1202982 (Why is no real title available?)
• scientific article; zbMATH DE number 2044946 (Why is no real title available?)
• 2-factor Hamiltonian graphs.
• A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter
• A new characterization of P_k-free graphs
• A new characterization of \(P_{6}\)-free graphs
• A note on matching-cut in \(P_t\)-free graphs
• A survey on the computational complexity of coloring graphs with forbidden subgraphs
• Algorithms solving the matching cut problem
• An FPT algorithm for matching cut and d-cut
• Clique-width for hereditary graph classes
• Computing vertex-surjective homomorphisms to partially reflexive trees
• Contracting to a longest path in H-free graphs
• Disconnected 2-factors in planar cubic bridgeless graphs
• Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
• Good edge-labelling of graphs
• Hard problems that quickly become very easy
• Matching cut in graphs with large minimum degree
• Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
• Matching cutsets in graphs
• Matching cutsets in graphs of diameter 2
• Networks immune to isolated line failures
• ON PRIMITIVE GRAPHS AND OPTIMAL VERTEX ASSIGNMENTS
• On stable cutsets in line graphs
• On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs
• Recognizing decomposable graphs
• Refined notions of parameterized enumeration kernels with applications to matching cut enumeration
• The complexity of the matching-cut problem for planar graphs and other graph classes
• The perfect matching cut problem revisited
• The structure of bull-free graphs II and III -- a summary
• The structure of claw-free graphs
• Vertex colouring and forbidden subgraphs -- a survey
• Vertex partitioning problems on graphs with bounded tree width

Cited in

(6)

• Finding a central vertex in an HHD-free graph
• Finding perfect matching cuts faster
• Dichotomies for maximum matching cut: \(H\)-freeness, bounded diameter, bounded radius
• Matching cutsets in graphs of diameter 2
• A note on matching-cut in \(P_t\)-free graphs
• Matching cut in graphs with large minimum degree

This page was built for publication: Finding matching cuts in \(H\)-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6046951)