On polynomial kernelization for stable cutset

DOI10.1016/J.DAM.2025.12.026MaRDI QIDQ6854635zbMATH OpenFDO

Authors Stefan Kratsch, Van Bang Le

Publication date 24 February 2026

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

Full work available at URL https://doi.org/10.1016/J.DAM.2025.12.026

zbMATH Keywords

independent cutsetkernelizationparameterized complexitystable cutset

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A completeness theory for polynomial (Turing) kernelization
• A note on fragile graphs
• Coloring graphs with stable cutsets
• Data reduction for graph coloring problems
• Dichotomies for maximum matching cut: \(H\)-freeness, bounded diameter, bounded radius
• Exact and parameterized algorithms for the independent cutset problem
• Extremal graphs having no stable cutset
• Finding small separators in linear time via treewidth reduction
• Fragile graphs with small independent cuts
• scientific article; zbMATH DE number 1161313 (Why is no real title available?)
• Kernel bounds for disjoint cycles and disjoint paths
• Kernelization Lower Bounds by Cross-Composition
• Matching cut in graphs with large minimum degree
• Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
• Matching cuts in graphs of high girth and H-free graphs
• Matching cutsets in graphs
• On polynomial kernelization for stable cutset
• ON PRIMITIVE GRAPHS AND OPTIMAL VERTEX ASSIGNMENTS
• On problems as hard as CNF-SAT
• On stable cutsets in claw-free graphs and planar graphs
• On stable cutsets in graphs
• On stable cutsets in line graphs
• Recognizing decomposable graphs
• Refined notions of parameterized enumeration kernels with applications to matching cut enumeration
• Stable set bonding in perfect graphs and parity graphs

This page was built for publication: On polynomial kernelization for stable cutset

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