Refined notions of parameterized enumeration kernels with applications to matching cut enumeration

DOI10.1016/j.jcss.2021.07.005zbMath1479.68002arXiv2101.03800OpenAlexW3187874026MaRDI QIDQ2237892

Dieter Kratsch, Van Bang Le, Christian Komusiewicz, Petr A. Golovach

Publication date: 28 October 2021

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

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

zbMATH Keywords

output-sensitive algorithmsenumeration problemskernelizationpolynomial delaystructural parameterizationsmatching cutsparameterized enumeration

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Related Items

Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts ⋮ Finding matching cuts in \(H\)-free graphs ⋮ Finding perfect matching cuts faster ⋮ The perfect matching cut problem revisited ⋮ The perfect matching cut problem revisited

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact exponential algorithms.
• Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
• Compactors for parameterized counting problems
• Algorithms solving the matching cut problem
• Linear delay enumeration and monadic second-order logic
• Fixed-parameter enumerability of cluster editing and related problems
• On problems without polynomial kernels
• On structural parameterizations of the matching cut problem
• Randomised enumeration of small witnesses using a decision oracle
• Algorithmic meta-theorems for restrictions of treewidth
• Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
• Analysis and enumeration. Algorithms for biological graphs
• Paradigms for parameterized enumeration
• A cubic-vertex kernel for flip consensus tree
• Approximating clique-width and branch-width
• Parameterized Algorithms for Modular-Width
• Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
• A better approximation ratio for the vertex cover problem
• Recognizing decomposable graphs
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Nondeterminism within $P^ * $
• Kernelization
• Approximating rank-width and clique-width quickly
• Lossy kernelization
• Kernelization Lower Bounds by Cross-Composition
• On the Enumeration of Minimal Dominating Sets and Related Notions
• A Polynomial Kernel for Proper Interval Vertex Deletion
• Kernelizations for Parameterized Counting Problems
• Parameterized Algorithms
• ON PRIMITIVE GRAPHS AND OPTIMAL VERTEX ASSIGNMENTS
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and Kernelization
• Parameterized aspects of triangle enumeration
• Matching cut in graphs with large minimum degree