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.
|Name||Lecture Notes in Computer Science|
|Conference||7th International Symposium on Parameterized and Exact Computation, IPEC 2012|
|Period||1/01/12 → …|