Feedback vertex set inspired kernel for chordal vertex deletion
From MaRDI portal
(Redirected from Feedback vertex set inspired kernel for chordal vertex deletion)
Feedback vertex set inspired kernel for chordal vertex deletion (scientific article; zbMATH DE number 7044615)
Feedback vertex set inspired kernel for chordal vertex deletion (scientific article; zbMATH DE number 7044615)
Abstract: Given a graph and a parameter , the Chordal Vertex Deletion (CVD) problem asks whether there exists a subset of size at most that hits all induced cycles of size at least 4. The existence of a polynomial kernel for CVD was a well-known open problem in the field of Parameterized Complexity. Recently, Jansen and Pilipczuk resolved this question affirmatively by designing a polynomial kernel for CVD of size , and asked whether one can design a kernel of size . While we do not completely resolve this question, we design a significantly smaller kernel of size , inspired by the -size kernel for Feedback Vertex Set. Furthermore, we introduce the notion of the independence degree of a vertex, which is our main conceptual contribution.
Recommendations
Cited in
(23)- Subexponential parameterized algorithms and kernelization on almost chordal graphs
- Towards constant-factor approximation for chordal/distance-hereditary vertex deletion
- Erdős-Pósa property of chordless cycles and its applications
- A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion
- Feedback vertex set inspired kernel for chordal vertex deletion
- Approximation and kernelization for chordal vertex deletion
- Approximation and kernelization for chordal vertex deletion
- scientific article; zbMATH DE number 7559376 (Why is no real title available?)
- scientific article; zbMATH DE number 7651188 (Why is no real title available?)
- Chordless Cycle Packing Is Fixed-Parameter Tractable
- A polynomial kernel for distance-hereditary vertex deletion
- A polynomial kernel for 3-leaf power deletion
- scientific article; zbMATH DE number 7765420 (Why is no real title available?)
- Polynomial Kernel for Interval Vertex Deletion
- A survey of parameterized algorithms and the complexity of edge modification
- A constant-factor approximation for weighted bond cover
- Smaller kernels for 3-leaf power modifications problems
- Tight bounds for chordal/interval vertex deletion parameterized by treewidth
- Hitting meets packing: how hard can it be?
- Subset feedback vertex set parameterized by multiway cut is FPT
- Parameterized geometric graph modification with disk scaling
- A polynomial kernel for proper Helly circular-arc vertex deletion
- A vertex incremental approach for maintaining chordality
This page was built for publication: Feedback vertex set inspired kernel for chordal vertex deletion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4629981)