A 14k-Kernel for Planar Feedback Vertex Set via Region Decomposition

Marthe Bonamy 1 Lukasz Kowalik 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We show a kernel of at most 14k vertices for the Planar Feedback Vertex Set problem. This improves over the previous kernel of size bounded by 97k. Our algorithm has a few new reduction rules. However, our main contribution is an application of the region decomposition technique in the analysis of the kernel size.
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01264417
Contributor : Alexandre Pinlou <>
Submitted on : Friday, January 29, 2016 - 11:57:04 AM
Last modification on : Tuesday, June 25, 2019 - 12:57:20 PM

Links full text

Identifiers

Collections

Citation

Marthe Bonamy, Lukasz Kowalik. A 14k-Kernel for Planar Feedback Vertex Set via Region Decomposition. IPEC: International Symposium on Parameterized and Exact Computation, Sep 2014, Wroclaw, Poland. pp.97-109, ⟨10.1007/978-3-319-13524-3_9⟩. ⟨lirmm-01264417⟩

Share

Metrics

Record views

233