Kernels for Edge Dominating Set: Simpler or Smaller

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

 ⊆ 

E

with |

D

| ≤ 

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 Xiao, Kloks and Poon, 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 ≤ 

k

is also an edge dominating set of the input graph. We then show that a refinement of the algorithm of Xiao, Kloks and Poon 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\}$

.