Feedback vertex set inspired kernel for chordal vertex deletion

DOI10.1145/3284356MaRDI QIDQ4629981zbMATH OpenOpenAlexFDO

Authors Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, Meirav Zehavi

Publication date 28 March 2019

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

chordal graphchordal vertex deletionkernelizationparameterized complexity

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Given a graph $G$ and a parameter $k$, the Chordal Vertex Deletion (CVD) problem asks whether there exists a subset $UsubseteqV(G)$ of size at most $k$ 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 $O(k^{161}lo{g}^{58}k)$, and asked whether one can design a kernel of size $O(k^{10})$. While we do not completely resolve this question, we design a significantly smaller kernel of size $O(k^{12}lo{g}^{10}k)$, inspired by the $O(k^2)$-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

• Feedback vertex set inspired kernel for chordal vertex deletion
• Approximation and kernelization for chordal vertex deletion
• Approximation and kernelization for chordal vertex deletion
• A polynomial kernel for block graph deletion
• A polynomial kernel for block graph deletion

Cited in

(22)

• 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
• 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)