Parameterized edge dominating set in graphs with degree bounded by 3

In this paper, we present an O∗(2.1479k)-time algorithm to decide whether a graph of maximum degree 3 has an edge dominating set of size at most k or not, which is based on enumeration of vertex covers and improves all previous results on this problem. We first enumerate partial vertex covers of size at most 2k and then construct an edge dominating set based on each vertex cover to find a required edge dominating set. To effectively enumerate vertex covers, we adopt a branch-and-reduce method, and use some techniques, such as ‘pseudo-cliques’ and ‘amortized transfer of cliques,’ to analyze the running time bound.