On Approximability of the Independent/Connected Edge Dominating Set Problems

Toshihiro Fujito

To appear at Foundations of Software Technology and Theoretical Computer Science (FSTTCS2000), New Delhi, India, December 13-15 2000


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)})$.

Server START Conference Manager
Update Time 14 Aug 2000 at 17:41:23
Maintainer fsttcs20@cse.iitd.ernet.in.
Start Conference Manager
Conference Systems