Algorithms and hardness results for edge total domination problem in graphs

For a graph G=(V,E) without an isolated edge, a set D⊆E is an edge total dominating set of G if every edge e∈E is adjacent to at least one edge of D. The MINIMUM EDGE TOTAL DOMINATING SET problem is to compute a minimum cardinality edge total dominating set of G. It is known that the decision version of the problem is NP-complete for bipartite graphs, chordal graphs, and planar graphs. On the positive side, the problem is efficiently solvable for trees. In this paper, we further study the complexity of this problem in other graph classes. We design a linear-time algorithm to compute a minimum cardinality edge total dominating set in chain graphs, a subclass of bipartite graphs. We also propose linear-time algorithms for two subclasses of chordal graphs, namely, split graphs and proper interval graphs with no cut vertices. In addition, we show that the problem is APX-complete for graphs with maximum degree 3 and propose an approximation algorithm for the problem in k-regular graphs, where k≥4. We discuss the complexity difference between the MINIMUM EDGE DOMINATING SET problem and MINIMUM EDGE TOTAL DOMINATING SET problem which seem to be closely related.