An improved kernel for the undirected planar feedback vertex set problem

Faisal Abu Khzam, M Bou Khuzam

Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedings

Abstract

We consider the parameterized Feedback Vertex Set problem on unweighted, undirected planar graphs. We present a kernelization algorithm that takes a planar graph G and an integer k as input and either decides that (G,k) is a no instance or produces an equivalent (kernel) instance (G′,k′) such that k′ ≤ k and |V(G′)| < 97k. In addition to the improved kernel bound (from 112kto 97k), our algorithm features simple linear-time reduction procedures that can be applied to the general Feedback Vertex Set problem.
Original languageEnglish
Title of host publicationParameterized and Exact Computation
Place of PublicationGermany
PublisherSpringer
Pages264-273
Number of pages10
Volume7535 LNCS
ISBN (Print)978-3-642-33292-0
DOIs
Publication statusPublished - 2012
Externally publishedYes
Event7th International Symposium on Parameterized and Exact Computation, IPEC 2012 - Ljubljana; Slovenia
Duration: 1 Jan 2012 → …

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume7535
ISSN (Print)0302-9743

Conference

Conference7th International Symposium on Parameterized and Exact Computation, IPEC 2012
Period1/01/12 → …

Fingerprint Dive into the research topics of 'An improved kernel for the undirected planar feedback vertex set problem'. Together they form a unique fingerprint.

Cite this