×

zbMATH — the first resource for mathematics

Linear-time computation of a linear problem kernel for dominating set on planar graphs. (English) Zbl 1352.68119
Marx, Dániel (ed.) et al., Parameterized and exact computation. 6th international symposium, IPEC 2011, Saarbrücken, Germany, September 6–8, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-28049-8/pbk). Lecture Notes in Computer Science 7112, 194-206 (2012).
Summary: We present a linear-time kernelization algorithm that transforms a given planar graph \(G\) with domination number \(\gamma (G)\) into a planar graph \(G^{\prime}\) of size \(O(\gamma (G))\) with \(\gamma (G) = \gamma (G^{\prime})\). In addition, a minimum dominating set for \(G\) can be inferred from a minimum dominating set for \(G^{\prime}\). In terms of parameterized algorithmics, this implies a linear-size problem kernel for the NP-hard Dominating Set problem on planar graphs, where the kernelization takes linear time. This improves on previous kernelization algorithms that provide linear-size kernels in cubic time.
For the entire collection see [Zbl 1238.68016].

MSC:
68Q25 Analysis of algorithms and problem complexity
05C10 Planar graphs; geometric and topological aspects of graph theory
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alber, J., Bodlaender, H.L., Fernau, H., Kloks, T., Niedermeier, R.: Fixed parameter algorithms for Dominating Set and related problems on planar graphs. Algorithmica 33(4), 461–493 (2002) · Zbl 1016.68055 · doi:10.1007/s00453-001-0116-5
[2] Alber, J., Fellows, M.R., Niedermeier, R.: Polynomial-time data reduction for dominating set. J. ACM 51(3), 363–384 (2004) · Zbl 1192.68337
[3] Alber, J., Betzler, N., Niedermeier, R.: Experiments on data reduction for optimal domination in networks. Ann. Oper. Res. 146(1), 105–117 (2006) · Zbl 1106.90011 · doi:10.1007/s10479-006-0045-4
[4] Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41(1), 153–180 (1994) · Zbl 0807.68067
[5] Bateni, M., Hajiaghayi, M., Marx, D.: Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth. In. In: Proc. 42th STOC, pp. 211–220. ACM Press (2010) · Zbl 1293.68308 · doi:10.1145/1806689.1806720
[6] Bodlaender, H.L.: Kernelization: New Upper and Lower Bound Techniques. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol. 5917, pp. 17–37. Springer, Heidelberg (2009) · Zbl 1273.68158 · doi:10.1007/978-3-642-11269-0_2
[7] Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) kernelization. In: Proc. 50th FOCS, pp. 629–638. IEEE (2009) · Zbl 1292.68089 · doi:10.1109/FOCS.2009.46
[8] Chen, J., Fernau, H., Kanj, I.A., Xia, G.: Parametric duality and kernelization: Lower bounds and upper bounds on kernel size. SIAM J. Comput. 37(4), 1077–1106 (2007) · Zbl 1141.05075 · doi:10.1137/050646354
[9] Chor, B., Fellows, M., Juedes, D.W.: Linear Kernels in Linear Time, or How to Save k Colors in O(n 2) Steps. In: Hromkovič, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol. 3353, pp. 257–269. Springer, Heidelberg (2004) · Zbl 1112.68412 · doi:10.1007/978-3-540-30559-0_22
[10] Dorn, F., Fomin, F.V., Thilikos, D.M.: Subexponential parameterized algorithms. Computer Science Review 2(1), 29–39 (2008) · Zbl 1302.68340 · doi:10.1016/j.cosrev.2008.02.004
[11] Fellows, M.R., Rosamond, F.A., Fomin, F.V., Lokshtanov, D., Saurabh, S., Villanger, Y.: Local search: Is brute-force avoidable? In: Proc. 21st IJCAI, pp. 486–491 (2009) · Zbl 1244.68070
[12] Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. In: Proc. 21st SODA, pp. 503–510. ACM/SIAM (2010) · Zbl 1288.68116 · doi:10.1137/1.9781611973075.43
[13] 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) · Zbl 1171.68488 · doi:10.1007/978-3-540-73420-8_34
[14] Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. SIGACT News 38(1), 31–45 (2007) · doi:10.1145/1233481.1233493
[15] Hagerup, T.: Linear-time kernelization for planar dominating set. In: Marx, D., Rossmanith, P. (eds.) IPEC 2011. LNCS, vol. 7112, pp. 181–193. Springer, Heidelberg (2012) · Zbl 1352.68109
[16] Wang, J., Yang, Y., Guo, J., Chen, J.: Linear Problem Kernels for Planar Graph Problems with Small Distance Property. In: Murlak, F., Sankowski, P. (eds.) MFCS 2011. LNCS, vol. 6907, pp. 592–603. Springer, Heidelberg (2011) · Zbl 1343.68123 · doi:10.1007/978-3-642-22993-0_53
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.