On approximability of the independent/connected edge dominating set problems

We investigate polynomial-time approximability of the problems related to e dge dominating sets of graphs. When edges are unit-weighted, the edge domin ating set problem is polynomially equivalent to the minimum maximal matchin g problem, in either exact or approximate computation, and the former probl em was recently found to be approximable within a factor of 2 even with arb itrary weights. It will be shown, in contrast with this, that the minimum w eight maximal matching problem cannot be approximated within any polynomial ly computable factor unless P = NP. The connected edge dominating set problem and the connected vertex cover pr oblem also have the same approximability when edges/vertices are unit-weigh ted. The former problem is already known to be approximable, even with gene ral edge weights, within a factor of 3.55. We will show that, when general weights are allowed, (1) the connected edge dominating set problem can be a pproximated within a factor of 3 + epsilon, and (2) the connected vertex co ver problem is approximable within a factor of lnn + 3 but cannot be within (1 - epsilon) lnn for any epsilon > 0 unless NP subset of DTIME(n(O(loglog n))). (C) 2001 Elsevier Science B.V. All rights reserved.