Algorithmic aspects of upper edge domination

Abstract We study the problem of finding a minimal edge dominating set of maximum size in a given graph G = ( V , E ) , called Upper EDS . We show that this problem is not approximable within a ratio of n e − 1 2 , for any e ∈ ( 0 , 1 2 ) , assuming P ≠ NP , where n = | V | . On the other hand, for graphs of minimum degree at least 2, we give an approximation algorithm with ratio 1 n , matching this lower bound. We further show that Upper EDS is APX -complete in bipartite graphs of maximum degree 4, and NP -hard in planar bipartite graphs of maximum degree 4.