zbMATH — the first resource for mathematics

Simpler linear-time kernelization for planar dominating set. (English) Zbl 1352.68109
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, 181-193 (2012).
Summary: We describe a linear-time algorithm that inputs a planar graph \(G\) and outputs a planar graph of size \(O(k)\) and with domination number \(k\), where \(k\) is the domination number of \(G\), i.e., the size of a smallest dominating set in \(G\). In the language of parameterized computation, the new algorithm is a linear-time kernelization for the NP-complete Planar Dominating Set problem that produces a kernel of linear size. Such an algorithm was previously known [R. van Bevern et al., Lect. Notes Comput. Sci. 7112, 194–206 (2012; Zbl 1352.68119)], but the new algorithm and its analysis are considerably simpler.
For the entire collection see [Zbl 1238.68016].

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)
Full Text: DOI
[1] Alber, J., Fellows, M.R., Niedermeier, R.: Polynomial-time data reduction for Dominating Set. J. ACM 51(3), 363–384 (2004) · Zbl 1192.68337 · doi:10.1145/990308.990309
[2] van Bevern, R., Hartung, S., Kammer, F., Niedermeier, R., Weller, M.: Linear-time computation of a linear problem kernel for Dominating Set on planar graphs. In: Marx, D., Rossmanith, P. (eds.) IPEC 2011. LNCS, vol. 7112, pp. 194–206. Springer, Heidelberg (2012) · Zbl 1352.68119
[3] Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) kernelization. In: FOCS, pp. 629–638. IEEE Computer Society (2009) · Zbl 1292.68089
[4] 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
[5] 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
[6] Jansen, B.: Kernelization for Maximum Leaf Spanning Tree with positive vertex weights. In: Calamoneri, T., Díaz, J. (eds.) CIAC 2010. LNCS, vol. 6078, pp. 192–203. Springer, Heidelberg (2010) · Zbl 1284.68298 · doi:10.1007/978-3-642-13073-1_18
[7] Kammer, F.: A linear-time algorithm to find a kernel for the Rooted Leaf Outbranching problem (2011) (manuscript)
[8] Kloks, T., Lee, C.M., Liu, J.: New algorithms for k-face cover, k-feedback vertex set, and k-disjoint cycles on plane and planar graphs. In: Kučera, L. (ed.) WG 2002. LNCS, vol. 2573, pp. 282–295. Springer, Heidelberg (2002) · Zbl 1022.68100 · doi:10.1007/3-540-36379-3_25
[9] Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006) · Zbl 1095.68038 · doi:10.1093/acprof:oso/9780198566076.001.0001
[10] Nishizeki, T., Chiba, N.: Planar Graphs: Theory and Algorithms. Dover Publications, Inc., Mineola (1988) · Zbl 0647.05001
[11] Protti, F., da Silva, M.D., Szwarcfiter, J.L.: Applying modular decomposition to parameterized cluster editing problems. Theory Comput. Syst. 44(1), 91–104 (2009) · Zbl 1179.68111 · doi:10.1007/s00224-007-9032-7
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.