Abstract
We prove a small linear-size kernel for the connected dominating set problem in planar graphs through data reduction. Our set of rules efficiently reduce a planar graph G with n vertices and connected dominating number γ c (G) to a kernel of size at most 413γ c (G) in O(n 3) time answering the question of whether the connectivity criteria hinders the construction of small kernels, negatively (in case of the planar connected dominating set). Our result gives a fixed-parameter algorithm of time \((2^{O(\sqrt{\gamma_c(G)})}\cdot \gamma_c(G) + n^3)\) using the standard branch-decomposition based approach.
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
Alber, J., Fellows, M.R., Niedermeier, R.: Polynomial-time data reduction for dominating set. Journal of the ACM 51(3), 363–384 (2004) (electronic)
Bansal, N., Blum, A., Chawla, S.: Correlation clustering, p. 238. IEEE Computer Society, Los Alamitos (2002)
Blum, J., Ding, M., Thaeler, A., Cheng, X.: Connected dominating set in sensor networks and MANETs. In: Handbook of combinatorial optimization, vol. B (Suppl.), pp. 329–369. Springer, New York (2005)
Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) Kernelization, April 4 (2009), http://arxiv.org/abs/0904.0727
Buss, J.F., Goldsmith, J.: Nondeterminism within P. SIAM Journal on Computing 22(3), 560–572 (1993)
Cai, L., Chen, J., Downey, R.G., Fellows, M.R.: Advice classes of parameterized tractability. Annals of Pure and Applied Logic 84(1), 119–138 (1997)
Chen, J., Fernau, H., Kanj, I.A., Xia, G.: Parametric duality and kernelization: Lower bounds and upper bounds on kernel size. SIAM Journal on Computing 37(4), 1077–1106 (2007)
Chen, J., Kanj, I.: Improved exact algorithms for MAX-SAT. In: Rajsbaum, S. (ed.) LATIN 2002. LNCS, vol. 2286, pp. 341–355. Springer, Heidelberg (2002)
Dorn, F.: Dynamic programming and fast matrix multiplication. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol. 4168, pp. 280–291. Springer, Heidelberg (2006)
Dorn, F., Penninkx, E., Bodlaender, H.L., Fomin, F.V.: Efficient exact algorithms on planar graphs: Exploiting sphere cut branch decompositions. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 95–106. Springer, Heidelberg (2005)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)
Gu, Q., Imani, N.: Small Kernel for Planar Connected Sominating Set. TR 2009-12, School of Computing Science, Simon Fraser University, Burnaby, BC, Canada (June 2009), ftp://fas.sfu.ca/pub/cs/TR/2009/CMPT2009-12.pdf
Guo, J., Niedermeier, R.: Linear Problem Kernels for NP-Hard Problems on Planar Graphs. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 375–386. Springer, Heidelberg (2007)
Gramm, J., Hirsch, E.A., Niedermeier, R., Rossmanith, P.: Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT. Discrete Applied Mathematics 130(2), 139–155 (2003)
Gramm, J., Nierhoff, T., Sharan, R., Tantau, T.: Haplotyping with missing data via perfect path phylogenies. Discrete Applied Mathematics 155(6-7), 788–805 (2007)
Guo, J., Niedermeier, R.: Fixed-parameter tractability and data reduction for multicut in trees. Networks 46(3), 124–135 (2005)
Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of Domination in Graphs. Monographs and Textbooks in Pure and Applied Mathematics, vol. 208. Marcel Dekker, New York (1998)
Imani, N.: Data Reduction for Connected Dominating Set. Master Thesis, Simon Fraser University, BC, Canada (August 2008)
Lokshtanov, D., Mnich, M., Saurabh, S.: Linear kernel for planar connected dominating set. To appear in Proceedings of TAMC (May 2009)
Mahajan, M., Raman, V.: Parameterizing above guaranteed values: MaxSat and MaxCut. Journal of Algorithms 31(2), 335–354 (1999)
Nemhauser, G.L., Trotter Jr., L.E.: Vertex packings: structural properties and algorithms. Mathematical Programming 8, 232–248 (1975)
Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications, vol. 31. Oxford University Press, Oxford (2006)
Weihe, K.: Covering trains by stations or the power of data reduction. In: Proceedings of Algorithms and Experiments, ALEX, pp. 1–8 (1998)
Weihe, K.: On the differences between “practical” and “applied”. In: Näher, S., Wagner, D. (eds.) WAE 2000. LNCS, vol. 1982, pp. 1–10. Springer, Heidelberg (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gu, Q., Imani, N. (2010). Connectivity Is Not a Limit for Kernelization: Planar Connected Dominating Set. In: López-Ortiz, A. (eds) LATIN 2010: Theoretical Informatics. LATIN 2010. Lecture Notes in Computer Science, vol 6034. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12200-2_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-12200-2_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-12199-9
Online ISBN: 978-3-642-12200-2
eBook Packages: Computer ScienceComputer Science (R0)