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

DOI10.1016/J.JCSS.2021.07.005MaRDI QIDQ2237892zbMATHOpenAlexFDO

Authors Christian Komusiewicz, Dieter Kratsch, Van Bang Le, 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

kernelizationpolynomial delayoutput-sensitive algorithmsenumeration problemsstructural parameterizationsmatching cutsparameterized enumeration

Mathematics Subject Classification ID

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

Abstract: An enumeration kernel as defined by Creignou et al. [Theory Comput. Syst. 2017] for a parameterized enumeration problem consists of an algorithm that transforms each instance into one whose size is bounded by the parameter plus a solution-lifting algorithm that efficiently enumerates all solutions from the set of the solutions of the kernel. We propose to consider two new versions of enumeration kernels by asking that the solutions of the original instance can be enumerated in polynomial time or with polynomial delay from the kernel solutions. Using the NP-hard Matching Cut problem parameterized by structural parameters such as the vertex cover number or the cyclomatic number of the input graph, we show that the new enumeration kernels present a useful notion of data reduction for enumeration problems which allows to compactly represent the set of feasible solutions.

Recommendations

• Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
• scientific article; zbMATH DE number 7378605
• Paradigms for parameterized enumeration
• Paradigms for parameterized enumeration
• Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and Kernelization

Cites work

• scientific article; zbMATH DE number 6515825 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2090012 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A Polynomial Kernel for Proper Interval Vertex Deletion
• A better approximation ratio for the vertex cover problem
• A cubic-vertex kernel for flip consensus tree
• Algorithmic meta-theorems for restrictions of treewidth
• Algorithms solving the matching cut problem
• Analysis and enumeration. Algorithms for biological graphs
• Approximating clique-width and branch-width
• Approximating rank-width and clique-width quickly
• Compactors for parameterized counting problems
• Data-compression for parametrized counting problems on sparse graphs
• Exact exponential algorithms.
• Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and Kernelization
• Fixed-parameter enumerability of cluster editing and related problems
• Kernelization Lower Bounds by Cross-Composition
• Kernelization. Theory of parameterized preprocessing
• Kernelizations for Parameterized Counting Problems
• Linear delay enumeration and monadic second-order logic
• Lossy kernelization
• Matching cut in graphs with large minimum degree
• Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
• Nondeterminism within $P^ * $
• ON PRIMITIVE GRAPHS AND OPTIMAL VERTEX ASSIGNMENTS
• On problems without polynomial kernels
• On structural parameterizations of the matching cut problem
• On the enumeration of minimal dominating sets and related notions
• Paradigms for parameterized enumeration
• Parameterized Algorithms for Modular-Width
• Parameterized algorithms
• Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
• Randomised enumeration of small witnesses using a decision oracle
• Recent developments in kernelization: a survey
• Recognizing decomposable graphs
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics

Cited in

(11)

• Paradigms for parameterized enumeration
• Finding perfect matching cuts faster
• Complexity Results for Matching Cut Problems in Graphs Without Long Induced Paths
• Cutting Barnette graphs perfectly is hard
• Parameterized enumeration for modification problems
• Dichotomies for maximum matching cut: \(H\)-freeness, bounded diameter, bounded radius
• Finding matching cuts in \(H\)-free graphs
• Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts
• The perfect matching cut problem revisited
• The perfect matching cut problem revisited
• Paradigms for parameterized enumeration

This page was built for publication: Refined notions of parameterized enumeration kernels with applications to matching cut enumeration

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