Abstract
We develop a generic framework for deriving linear-size problem kernels for NP-hard problems on planar graphs. We demonstrate the usefulness of our framework in several concrete case studies, giving new kernelization results for Connected Vertex Cover, Minimum Edge Dominating Set, Maximum Triangle Packing, and Efficient Dominating Set on planar graphs. On the route to these results, we present effective, problem-specific data reduction rules that are useful in any approach attacking the computational intractability of these problems.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Abu-Khzam, F.N., Collins, R.L., Fellows, M.R., Langston, M.A., Suters, W.H., Symons, C.T.: Kernelization algorithms for the Vertex Cover problem: theory and experiments. In: Proc. 6th ACM-SIAM ALENEX, pp. 62–69. ACM Press, New York (2004)
Alber, J., Betzler, N., Niedermeier, R.: Experiments on data reduction for optimal domination in networks. Annals of Operations Research 146(1), 105–117 (2006)
Alber, J., Dorn, B., Niedermeier, R.: A general data reduction scheme for domination in graphs. In: Wiedermann, J., Tel, G., Pokorný, J., Bieliková, M., Štuller, J. (eds.) SOFSEM 2006. LNCS, vol. 3831, pp. 137–147. Springer, Heidelberg (2006)
Alber, J., Fellows, M.R., Niedermeier, R.: Polynomial time data reduction for Dominating Set. Journal of the ACM 51(3), 363–384 (2004)
Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM 41(1), 153–180 (1994)
Bange, D.W., Barkauskas, A.E., Slater, P.J.: Efficient dominating sets in graphs. In: Proc. 3rd Conference on Discrete Mathematics. SIAM, pp. 189–199 (1988)
Chen, J., Fernau, H., Kanj, I.A., Xia, G.: Parametric duality and kernelization: Lower bounds and upper bounds on kernel size. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol. 3404, pp. 269–280. Springer, Heidelberg (2005)
Chen, J., Kanj, I.A., Jia, W.: Vertex Cover: Further observations and further improvements. Journal of Algorithms 41, 280–301 (2001)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)
Fellows, M.R., Heggernes, P., Rosamond, F.A., Sloper, C., Telle, J.A.: Finding k disjoint triangles in an arbitrary graph. In: Hromkovič, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol. 3353, pp. 235–244. Springer, Heidelberg (2004)
Fellows, M.R., Hoover, M.: Perfect domination. Australian Journal of Combinatorics 3, 141–150 (1991)
Fomin, F.V., Thilikos, D.M.: Fast parameterized algorithms for graphs on surfaces: Linear kernel and exponential speed-up. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 581–592. Springer, Heidelberg (2004)
Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem is NP-complete. SIAM Journal on Applied Mathematics 32, 826–834 (1977)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)
Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. SIGACT News 38(1), 31–45 (2007)
Guo, J., Niedermeier, R., Wernicke, S.: Parameterized complexity of generalized Vertex Cover problems. In: Dehne, F., López-Ortiz, A., Sack, J.-R. (eds.) WADS 2005. LNCS, vol. 3608, pp. 36–48. Springer, Heidelberg (2005) Long version to appear under the title Parameterized complexity of Vertex Cover variants in Theory of Computing Systems
Guo, J., Niedermeier, R., Wernicke, S.: Fixed-parameter tractability results for full-degree spanning tree and its dual. In: Fischer, K., Timm, I.J., André, E., Zhong, N. (eds.) MATES 2006. LNCS (LNAI), vol. 4196, pp. 203–214. Springer, Heidelberg (2006)
Lu, C.L., Tang, C.Y.: Weighted efficient domination problem on some perfect graphs. Discrete Applied Mathematics 117, 163–182 (2002)
Moser, H., Sikdar, S.: The parameterized complexity of the induced matching problem in planar graphs. In: FAW 2007. Proc. 1st International Frontiers of Algorithmics Workshop. LNCS, Springer, Heidelberg (2007)
Nemhauser, G.L., Trotter, L.E.: Vertex packing: structural properties and algorithms. Mathematical Programming 8, 232–248 (1975)
Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)
Prieto, E.: Systematic Kernelization in FPT Algorithm Design. PhD thesis, Department of Computer Science, University of Newcastle, Australia (2005)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Guo, J., Niedermeier, R. (2007). Linear Problem Kernels for NP-Hard Problems on Planar Graphs. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds) Automata, Languages and Programming. ICALP 2007. Lecture Notes in Computer Science, vol 4596. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73420-8_34
Download citation
DOI: https://doi.org/10.1007/978-3-540-73420-8_34
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73419-2
Online ISBN: 978-3-540-73420-8
eBook Packages: Computer ScienceComputer Science (R0)