Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion

Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion Given a graph G and a parameter k, the Chordal Vertex Deletion (CVD) problem asks whether there exists a subset U V(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 (k161 log58k) and asked whether one can design a kernel of size O (k10) Jansen an Pilipczuk, SODA 2017. While we do not completely resolve this question, we design a significantly smaller kernel of size O (k12 log10k), inspired by the O (k2) -size kernel for Feedback Vertex Set Thomassé, TALG 2010. Furthermore, we introduce the notion of the independence degree of a vertex, which is our main conceptual contribution. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Algorithms (TALG) Association for Computing Machinery

Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion

Download PDF
28 pages

Loading next page...
 
/lp/association-for-computing-machinery/feedback-vertex-set-inspired-kernel-for-chordal-vertex-deletion-LpQYSm6T7h
Publisher
Association for Computing Machinery
Copyright
Copyright © 2018 ACM
ISSN
1549-6325
eISSN
1549-6333
DOI
10.1145/3284356
Publisher site
See Article on Publisher Site

Abstract

Given a graph G and a parameter k, the Chordal Vertex Deletion (CVD) problem asks whether there exists a subset U V(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 (k161 log58k) and asked whether one can design a kernel of size O (k10) Jansen an Pilipczuk, SODA 2017. While we do not completely resolve this question, we design a significantly smaller kernel of size O (k12 log10k), inspired by the O (k2) -size kernel for Feedback Vertex Set Thomassé, TALG 2010. Furthermore, we introduce the notion of the independence degree of a vertex, which is our main conceptual contribution.

Journal

ACM Transactions on Algorithms (TALG) – Association for Computing Machinery

Published: Dec 8, 2018

Keywords: Chordal vertex deletion

References

  • A kernelization algorithm for d-hitting set
    Abu-Khzam, Faisal N.
  • Kernelization algorithms for the vertex cover problem: Theory and experiments
    Abu-Khzam, Faisal N.; Collins, Rebecca L.; Fellows, Michael R.; Langston, Michael A.; Suters, W. Henry; Symons, Christopher T.
  • Polylogarithmic approximation algorithms for weighted-F-deletion problems
    Agrawal, Akanksha; Lokshtanov, Daniel; Misra, Pranabendu; Saurabh, Saket; Zehavi, Meirav
  • Solving MAX-r-SAT above a tight lower bound
    Alon, Noga; Gutin, Gregory; Kim, Eun Jung; Szeider, Stefan; Yeo, Anders
  • On problems without polynomial kernels
    Bodlaender, Hans L.; Downey, Rodney G.; Fellows, Michael R.; Hermelin, Danny
  • (Meta) kernelization
    Bodlaender, Hans L.; Fomin, Fedor V.; Lokshtanov, Daniel; Penninkx, Eelko; Saurabh, Saket; Thilikos, Dimitrios M.
  • Preprocessing for treewidth: A combinatorial analysis through kernelization
    Bodlaender, Hans L.; Jansen, Bart M. P.; Kratsch, Stefan
  • Linear recognition of almost interval graphs
    Cao, Yixin
  • Interval deletion is fixed-parameter tractable
    Cao, Yixin; Marx, Dániel
  • Chordal editing is fixed-parameter tractable
    Cao, Yixin; Marx, Dániel
  • Vertex cover: Further observations and further improvements
    Chen, Jianer; Kanj, Iyad A.; Jia, Weijia
  • Parameterized Algorithms
    Cygan, Marek; Fomin, Fedor V.; Kowalik, Łukasz; Lokshtanov, Daniel; Marx, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket
  • Open problems from workshop on kernels
    Cygan, Marek; Kowalik, Lukasz; Pilipczuk, Marcin
  • Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
    Dell, Holger; van Melkebeek, Dieter
  • Fundamentals of Parameterized Complexity
    Downey, Rodney G.; Fellows, Michael R.
  • Parameterized Complexity Theory
    Flum, Jörg; Grohe, Martin
  • Planar F-deletion: Approximation, kernelization and optimal FPT algorithms
    Fomin, Fedor V.; Lokshtanov, Daniel; Misra, Neeldhara; Saurabh, Saket
  • Bidimensionality and kernels
    Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Thilikos, Dimitrios M.
  • A polynomial kernel for proper interval vertex deletion
    Fomin, Fedor V.; Saurabh, Saket; Villanger, Yngve
  • Infeasibility of instance compression and succinct PCPs for NP
    Fortnow, Lance; Santhanam, Rahul
  • A unified approximation algorithm for node-deletion problems
    Fujito, Toshihiro
  • Uniform kernelization complexity of hitting forbidden minors
    Giannopoulou, Archontia C.; Jansen, Bart M. P.; Lokshtanov, Daniel; Saurabh, Saket
  • Algorithmic Graph Theory and Perfect Graphs
    Golumbic, Martin Charles
  • Parameterized complexity of vertex deletion into perfect graph classes
    Heggernes, Pinar; Hof, Pim van’t; Jansen, Bart M. P.; Kratsch, Stefan; Villanger, Yngve
  • Turing kernelization for finding long paths and cycles in restricted graph classes
    Jansen, Bart M. P.
  • Approximation and kernelization for chordal vertex deletion
    Jansen, Bart M. P.; Pilipczuk, Marcin
  • Unit interval vertex deletion: Fewer vertices are relevant
    Ke, Yuping; Cao, Yixin; Ouyang, Xiating; Wang, Jianxin
  • Linear kernels and single-exponential algorithms via protrusion decompositions
    Kim, Eun Jung; Langer, Alexander; Paul, Christophe; Reidl, Felix; Rossmanith, Peter; Sau, Ignasi; Sikdar, Somnath
  • Polynomial kernelizations for MIN F+Π1 and MAX NP
    Kratsch, Stefan
  • Recent developments in kernelization: A survey
    Kratsch, Stefan
  • Representative sets and irrelevant vertices: New tools for kernelization
    Kratsch, Stefan; Wahlström, Magnus
  • Compression via matroids: A randomized polynomial kernel for odd cycle transversal
    Kratsch, Stefan; Wahlström, Magnus
  • The node-deletion problem for hereditary properties is NP-complete
    Lewis, John M.; Yannakakis, Mihalis
  • Kernelization—Preprocessing with a guarantee
    Lokshtanov, Daniel; Misra, Neeldhara; Saurabh, Saket
  • On the hardness of approximating minimization problems
    Lund, Carsten; Yannakakis, Mihalis
  • Chordal deletion is fixed-parameter tractable
    Marx, Dániel
  • Finding small separators in linear time via treewidth reduction
    Marx, Dániel; O’Sullivan, Barry; Razgon, Igor
  • Invitation to Fixed-Parameter Algorithms
    Niedermeier, Rolf
  • Network sparsification for steiner problems on planar and bounded-genus graphs
    Pilipczuk, Marcin; Pilipczuk, Michal; Sankowski, Piotr; van Leeuwen, Erik Jan
  • A 4k2 kernel for feedback vertex set
    Thomassé, Stéphan
  • Node- and edge-deletion NP-complete problems
    Yannakakis, Mihalis