We investigate polynomial-time approximability of the problems related
to edge dominating sets of graphs.
When edges are unit-weighted, the edge dominating set problem is
polynomially equivalent to the minimum maximal matching problem, in
either exact or approximate computation, and the former problem was
recently found to be approximable within a factor of 2.1 even with
arbitrary weights. It will be shown, in contrast with this, that the
minimum weight maximal matching problem cannot be approximated within
any polynomially computable factor unless P=NP.
The connected edge dominating set problem and the connected vertex
cover problem also have the same approximability when edges/vertices
are unit-weighted, and the former problem is known to be approximable,
even with general edge weights, within a factor of 3.598.
We will show that, when general weights are allowed,
1) the connected edge dominating set problem can be approximated
within a factor of $3+\epsilon$, and
2) the connected vertex cover problem is approximable within a factor
of $3+\ln n$ but cannot be within $(1-\epsilon)\ln n$ for any $\epsilon >0$
unless $\mbox{NP}\subset \mbox{DTIME}(n^{O(\log\log n)})$.
