Skip to Main content Skip to Navigation
Conference papers

A 14$k$-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

Cited literature [23 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01264417
Contributor : Alexandre Pinlou <>
Submitted on : Tuesday, February 4, 2020 - 3:54:22 PM
Last modification on : Monday, June 8, 2020 - 9:48:02 AM
Document(s) archivé(s) le : Tuesday, May 5, 2020 - 5:54:56 PM

File

1410.8336.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Marthe Bonamy, Lukasz Kowalik. A 14$k$-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

325

Files downloads

145