Abstract
We show that any instance I of the Feedback Vertex Set problem in undirected planar graphs can be reduced to an equivalent instance I′ such that (i) the size of the instance and the size of the minimum feedback vertex set do not increase, (ii) and the size of the minimum feedback vertex set in I′ is at least \({\frac{1}{29}}\) of the number of vertices in I′. This implies a 29k kernel for this problem with parameter k being the size of the feedback vertex set. Our result improves the previous results of 97k and 112k.
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
Preview
Unable to display preview. Download preview PDF.
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)
Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) kernelization. In: FOCS 2009, pp. 629–638. IEEE Computer Society, Washington, DC (2009)
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)
Bodlaender, H.L., van Dijk, T.C.: A Cubic Kernel for Feedback Vertex Set and Loop Cutset. Theory Comput. Syst. 46(3), 566–597 (2010)
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)
Cao, Y., Chen, J., Liu, Y.: On feedback vertex set new measure and new structures. In: Kaplan, H. (ed.) SWAT 2010. LNCS, vol. 6139, pp. 93–104. Springer, Heidelberg (2010)
Chen, J., Fomin, F., Liu, Y., Lu, S., Villanger, Y.: Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci. 74, 1188–1198 (2008)
Chen, J., Liu, Y., Lu, S., O’Sullivan, B., Razgon, I.: A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM 55, 1–19 (2008)
Dehne, F., Fellows, M.R., Langston, M.A., Rosamond, F.A., Stevens, K.: An O(2O(k) n 3) FPT algorithm for the undirected feedback vertex set problem. In: Wang, L. (ed.) COCOON 2005. LNCS, vol. 3595, pp. 859–869. Springer, Heidelberg (2005)
Fomin, F.V., Gaspers, S., Pyatkin, A.V., Razgon, I.: On the minimum feedback vertex set problem: Exact and enumeration algorithms. Algorithmica 52(2), 293–307 (2008)
Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. In: SODA 2010, Philadelphia, PA, USA, pp. 503–510 (2010)
Garey, M.R., Johnson, D.S.: Computers and intractability: A guide to the theory of NP-completeness. Freeman, San Francisco (1979)
Guo, J., Gramm, J., Huffner, F., Niedermeier, R., Wernicke, S.: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. J. Comput. Syst. Sci. 72(8), 1386–1396 (2006)
Razgon, I.: Exact computation of maximum induced forest. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol. 4059, pp. 160–171. Springer, Heidelberg (2006)
Razgon, I.: Computing minimum directed feedback vertex set in O(1.9977n). In: 10th Italian Conference on Theoretical Computer Science, ICTCS 2007, Rome, Italy, pp. 70–81 (2007)
Silberschatz, A., Galvin, P.: Operating System Concepts, 4th edn. Addison-Wesley (1994)
Thomassé, S.: A 4k 2 kernel for feedback vertex set. ACM Transactions on Algorithms 6(2) (2010)
Xiao, M., Nagamochi, H.: An Improved Exact Algorithm for Undirected Feedback Vertex Set. Journal of Combinatorial Optimization (2014), doi: 10.1007/s10878-014-9737-x; A preliminary version appears as: Xiao, M., Nagamochi, H.: An Improved Exact Algorithm for Undirected Feedback Vertex Set. In: Widmayer, P., Xu, Y., Zhu, B. (eds.) COCOA 2013. LNCS, vol. 8287, pp. 153–164. Springer, Heidelberg (2013)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Xiao, M. (2014). A New Linear Kernel for Undirected Planar Feedback Vertex Set: Smaller and Simpler. In: Gu, Q., Hell, P., Yang, B. (eds) Algorithmic Aspects in Information and Management. AAIM 2014. Lecture Notes in Computer Science, vol 8546. Springer, Cham. https://doi.org/10.1007/978-3-319-07956-1_26
Download citation
DOI: https://doi.org/10.1007/978-3-319-07956-1_26
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-07955-4
Online ISBN: 978-3-319-07956-1
eBook Packages: Computer ScienceComputer Science (R0)