zbMATH — the first resource for mathematics

Linear problem kernels for planar graph problems with small distance property. (English) Zbl 1343.68123
Murlak, Filip (ed.) et al., Mathematical foundations of computer science 2011. 36th international symposium, MFCS 2011, Warsaw, Poland, August 22–26, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22992-3/pbk). Lecture Notes in Computer Science 6907, 592-603 (2011).
Summary: Recently, various linear problem kernels for NP-hard planar graph problems have been achieved, finally resulting in a meta-theorem for classification of problems admitting linear kernels. Almost all of these results are based on a so-called region decomposition technique. In this paper, we introduce a simple partition of the vertex set to analyze kernels for planar graph problems which admit the distance property with small constants. Without introducing new reduction rules, this vertex partition directly leads to improved kernel sizes for several problems. Moreover, we derive new kernelization algorithms for Connected Vertex Cover, Edge Dominating Set, and Maximum Triangle Packing problems, further improving the kernel size upper bounds for these problems.
For the entire collection see [Zbl 1219.68020].

68Q25 Analysis of algorithms and problem complexity
05C10 Planar graphs; geometric and topological aspects of graph theory
05C12 Distance in graphs
Full Text: DOI