International Symposium on Parameterized and Exact Computation

Abu-Khzam, Faisal N.; Bou Khuzam, Mazen

International Symposium on Parameterized and Exact Computation

Title: International Symposium on Parameterized and Exact Computation;
An improved kernel for the undirected planar feedback vertex set problem

Abu-Khzam, Faisal N.; Bou Khuzam, Mazen; SAS; 200302941; Computer Science and Mathematics; faisal.abukhzam@lau.edu.lb; Lebanese American University

URI: http://hdl.handle.net/10725/5379

URL: https://link.springer.com/chapter/10.1007/978-3-642-33293-7_25

DOI: http://dx.doi.org/10.1007/978-3-642-33293-7_25

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 112k to 97k), our algorithm features simple linear-time reduction procedures that can be applied to the general Feedback Vertex Set problem.

Citation:

Abu-Khzam, F. N., & Khuzam, M. B. (2012, September). An improved kernel for the undirected planar feedback vertex set problem. In International Symposium on Parameterized and Exact Computation (pp. 264-273). Springer Berlin Heidelberg.