zbMATH — the first resource for mathematics

Kernels for edge dominating set: simpler or smaller. (English) Zbl 1365.68281
Rovan, Branislav (ed.) et al., Mathematical foundations of computer science 2012. 37th international symposium, MFCS 2012, Bratislava, Slovakia, August 27–31, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-32588-5/pbk). Lecture Notes in Computer Science 7464, 491-502 (2012).
Summary: A kernelization for a parameterized computational problem is a polynomial-time procedure that transforms every instance of the problem into an equivalent instance (the so-called kernel) whose size is bounded by a function of the value of the chosen parameter. We present new kernelizations for the NP-complete Edge Dominating Set problem which asks, given an undirected graph \(G = (V,E)\) and an integer \(k\), whether there exists a subset \(D \subseteq E\) with \(|D| \leq k\) such that every edge in \(E\) shares at least one endpoint with some edge in \(D\). The best previous kernelization for Edge Dominating Set, due to M. Xiao et al. [Lect. Notes Comput. Sci. 6907, 604–615 (2011; Zbl 1343.68125)], yields a kernel with at most \(2 k ^{2} + 2 k\) vertices in linear time. We first describe a very simple linear-time kernelization whose output has at most \(4 k ^{2} + 4 k\) vertices and is either a trivial “no” instance or a vertex-induced subgraph of the input graph in which every edge dominating set of size \(\leq k\) is also an edge dominating set of the input graph. We then show that a refinement of the algorithm of [loc. cit.] and a different analysis can lower the bound on the number of vertices in the kernel by a factor of about 4, namely to \(\max\{\frac{1}{2}k^2+\frac{7}{2}k,6 k\}\).
For the entire collection see [Zbl 1246.68054].

68Q25 Analysis of algorithms and problem complexity
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
Full Text: DOI