A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter

DOI10.1016/j.tcs.2018.10.029zbMath1422.68125arXiv1804.11102OpenAlexW2798321768MaRDI QIDQ1740696

Van Bang Le, Hoàng-Oanh Le

Publication date: 2 May 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitygraph algorithmNP-hardnessdichotomy theoremdecomposable graphmatching cut

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (9)

Finding matching cuts in \(H\)-free graphs ⋮ Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms ⋮ Perfectly matched sets in graphs: parameterized and exact computation ⋮ The perfect matching cut problem revisited ⋮ The perfect matching cut problem revisited ⋮ Matching cut in graphs with large minimum degree ⋮ On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs ⋮ A note on matching-cut in \(P_t\)-free graphs ⋮ An FPT algorithm for matching cut and d-cut

Cites Work

• Unnamed Item
• Unnamed Item
• Algorithms solving the matching cut problem
• Matching cutsets in graphs of diameter 2
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• On stable cutsets in line graphs
• Diameter and treewidth in minor-closed graph families
• Recognizing decomposable graphs
• Easy problems for tree-decomposable graphs
• The complexity of the matching-cut problem for planar graphs and other graph classes
• Networks immune to isolated line failures
• On the Complexity of Timetable and Multicommodity Flow Problems
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Matching cutsets in graphs
• A Computing Procedure for Quantification Theory
• ON PRIMITIVE GRAPHS AND OPTIMAL VERTEX ASSIGNMENTS
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Good edge-labelling of graphs

This page was built for publication: A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter