__
TR97-004 | 19th February 1997 00:00
__

#### Approximating Dense Cases of Covering Problems

**Abstract:**
We study dense instances of several covering problems. An instance of

the set cover problem with $m$ sets is dense if there is $\epsilon>0$

such that any element belongs to at least $\epsilon m$ sets. We show

that the dense set cover problem can be approximated with the

performance ratio $c\log n$ for any $c>0$ and it is unlikely to be

NP-hard. We construct a polynomial-time approximation scheme for the

dense Steiner tree problem in $n$-vertex graphs, i.e. for the case

when each terminal is adjacent to at least $\epsilon n$ vertices. We

also study the vertex cover problem in $\epsilon$-dense graphs.

Though this problem is shown to be still MAX-SNP-hard as in general

graphs, we find a better approximation algorithm with the performance

ratio $2\over{1+\epsilon}$. The {\em superdense} cases of all these

problems are shown to be solvable in polynomial time.

__
Comment #1 to TR97-004 | 30th April 1998 15:05
__
#### Evaluation of an Approximate Algorithm for the Everywhere Dense Vertex Cover Problem Comment on: TR97-004

**Abstract:**
We generalize the DVC algorithm for the weighted case of vertex cover

problem (VCP) and study the performance of this algorithm. An extension

of result from TR97-004 for the weighted case is proposed in terms of a

new density parameter. Given a graph $G(V,E)$ let there be $\rho >0$

such that $w(O(v)) \geq \rho w(V)$ for any vertex $v \in V$. Here

$w(O(v))$ is the total weight of the neighbours of $v$, and $w(V)$ is

the total weight of $V$. Then $\frac{2}{1+\rho}$ performance guarantee

holds for an algorithm similar to DVC. The value $\rho$ can be easily

estimated for everywhere $\varepsilon$-dense VCP, if there is such $d$

that $w_u \leq dw_v$ for any pair of vertices $u$ and $v$. The

generalization of DVC allows us to propose another polinomial-time

algorithm for the weighted VCP with the performance ratio as a function

on $|V|$ which is less than $\frac{2}{1+\rho}$.