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

DOI10.1016/J.JCSS.2021.07.005zbMATH Open1479.68002arXiv2101.03800OpenAlexW3187874026MaRDI QIDQ2237892FDOQ2237892

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

Publication date: 28 October 2021

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

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.

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

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

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)

Cites Work

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

Cited In (8)

• Cutting Barnette graphs perfectly is hard
• Finding perfect matching cuts faster
• Dichotomies for maximum matching cut: \(H\)-freeness, bounded diameter, bounded radius
• 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
• Complexity Results for Matching Cut Problems in Graphs Without Long Induced Paths
• Finding matching cuts in \(H\)-free graphs

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)