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.
Work partially supported by the ANR Grant EGOS (2012–2015) 12 JS02 002 01 (MB) and by the National Science Centre of Poland, grant number UMO-2013/09/B/ST6/03136 (ŁK).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Abu-Khzam, F.N., Bou Khuzam, M.: An improved kernel for the undirected planar feedback vertex set problem. In: Thilikos, D.M., Woeginger, G.J. (eds.) IPEC 2012. LNCS, vol. 7535, pp. 264–273. Springer, Heidelberg (2012)
Alber, J., Fellows, M.R., Niedermeier, R.: Polynomial-time data reduction for dominating set. J. ACM 51(3), 363–384 (2004)
Bodlaender, H.L.: A cubic kernel for feedback vertex set. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol. 4393, pp. 320–331. Springer, Heidelberg (2007)
Bodlaender, H.L., Penninkx, E.: A linear kernel for planar feedback vertex set. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol. 5018, pp. 160–171. Springer, Heidelberg (2008)
Burrage, K., Estivill-Castro, V., Fellows, M.R., Langston, M.A., Mac, S., Rosamond, F.A.: The undirected feedback vertex set problem has a poly(k) kernel. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 192–202. Springer, Heidelberg (2006)
Festa, P., Pardalos, P., Resende, M.: Feedback Set Problems. Encyclopedia of Optimization, pp. 1005–1016. Springer, New York (2009)
Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. In: SODA, pp. 503–510 (2010)
Karp, R.: Reducibility among combinatorial problems. In: Miller, R., Thatcher, J. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972)
Silberschatz, A., Galvin, P.B., Gagne, G.: Operating System Concepts, 8th edn. Wiley Publishing, New York (2008)
Thomassé, S.: A \(4k^2\) kernel for feedback vertex set. ACM Trans. Algorithms 6(2), 1–8 (2010)
Xiao, M.: A new linear kernel for undirected planar feedback vertex set: smaller and simpler. In: Gu, Q., Hell, P., Yang, B. (eds.) AAIM 2014. LNCS, vol. 8546, pp. 288–298. Springer, Heidelberg (2014)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Bonamy, M., Kowalik, Ł. (2014). A \(14k\)-Kernel for Planar Feedback Vertex Set via Region Decomposition. In: Cygan, M., Heggernes, P. (eds) Parameterized and Exact Computation. IPEC 2014. Lecture Notes in Computer Science(), vol 8894. Springer, Cham. https://doi.org/10.1007/978-3-319-13524-3_9
Download citation
DOI: https://doi.org/10.1007/978-3-319-13524-3_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-13523-6
Online ISBN: 978-3-319-13524-3
eBook Packages: Computer ScienceComputer Science (R0)