New parameterized algorithms for the edge dominating set problem

An edge dominating set of a graph G = ( V, E ) is a subset M ⊆ E of edges in the graph such that each edge in E − M is incident with at least one edge in M. In an instance of the parameterized edge dominating set problem, we are given a graph G = ( V, E ) and an integer k, and we are asked to decide whether G has an edge dominating set of size at most k. In this paper, we show that the parameterized edge dominating set problem can be solved in O ∗ ( 2. 314 7 k ) time and polynomial space. We also show that this problem can be reduced to a quadratic kernel with O ( k 3 ) edges.

Authors

• Mingyu Xiao
• Ton Kloks
• Sheung-Hung Poon

Keywords

• Graph algorithms
• Parameterized algorithms
• Kernelization
• Edge dominating set