Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms

DOI10.1016/J.DAM.2019.12.010MaRDI QIDQ2192064zbMATH OpenOpenAlexWikidataFDO

Authors Christian Komusiewicz, Dieter Kratsch, Van Bang Le

Publication date 29 June 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2019/10220/

zbMATH Keywords

kernelizationNP-hard problembranching algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• scientific article; zbMATH DE number 7378605
• Algorithms solving the matching cut problem
• Algorithms Solving the Matching Cut Problem
• Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and Kernelization
• Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization

Cites work

• scientific article; zbMATH DE number 2044946 (Why is no real title available?)
• 3-SAT faster and simpler -- unique-SAT bounds for PPSZ hold in general
• A Computing Procedure for Quantification Theory
• A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter
• A fast branching algorithm for cluster vertex deletion
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Algorithms solving the matching cut problem
• An improved exponential-time algorithm for k -SAT
• Chain, generalization of covering code, and deterministic algorithm for \(k\)-SAT
• Exact exponential algorithms.
• Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and Kernelization
• Finding small separators in linear time via treewidth reduction
• Fundamentals of parameterized complexity
• Good edge-labelling of graphs
• Kernelization Lower Bounds by Cross-Composition
• Matching cut in graphs with large minimum degree
• 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 structural parameterizations of the matching cut problem
• On the Complexity of Timetable and Multicommodity Flow Problems
• Parameterized algorithms
• Recognizing decomposable graphs
• The complexity of the matching-cut problem for planar graphs and other graph classes

Cited in

(18)

• Finding matching cuts in \(H\)-free graphs
• Vertex partitioning problems on graphs with bounded tree width
• Cutting Barnette graphs perfectly is hard
• FPT and kernelization algorithms for the induced tree problem
• Refined notions of parameterized enumeration kernels with applications to matching cut enumeration
• scientific article; zbMATH DE number 7378605 (Why is no real title available?)
• A survey of parameterized algorithms and the complexity of edge modification
• Dichotomies for maximum matching cut: \(H\)-freeness, bounded diameter, bounded radius
• The perfect matching cut problem revisited
• The perfect matching cut problem revisited
• Algorithms solving the matching cut problem
• Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and Kernelization
• A single exponential-time FPT algorithm for cactus contraction
• Perfectly matched sets in graphs: parameterized and exact computation
• On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs
• An FPT algorithm for matching cut and d-cut
• Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
• Matching cut in graphs with large minimum degree

This page was built for publication: Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms

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