# 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].

##### MSC:
 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: