Highest-Degree First Maximum Vertex Coverage Algorithm

Definition

Highest-Degree First Maximum Vertex Coverage Algorithm

For Maximum Vertex Coverage on $G=(V,E)$ with budget $k$, select the $h=\min (k,|V|)$ vertices of highest original degree. Degrees are not recomputed after selections. The returned set $A$ satisfies
$|\mathrm{cov}(A)|\ge \mathrm{OPT}-\left(\genfrac{}{}{0ex}{}{h}{2}\right).$
For $1\le k\le |V|$ and $0<\epsilon <1$, if the maximum degree $\Delta >\left(\genfrac{}{}{0ex}{}{k}{2}\right)/\epsilon$, then $|\mathrm{cov}(A)|\ge (1-\epsilon )\mathrm{OPT}$.

Algorithm

compute every vertex degree
sort v[1],...,v[n] by nonincreasing degree
return {v[1],...,v[min(k,n)]}

Sorting and degree computation take $O(|V|\log (|V|+1)+|E|)$ time. If $k=0$, return the empty set. If $k\ge |V|$, selecting all vertices is optimal.

Counting covered edges

Degree sum counts internal edges twice

For $X\subseteq V$, let $D(X)={\sum }_{v\in X}\mathrm{deg}(v)$ and let $E[X]$ be the edges with both endpoints in $X$. An internal edge contributes twice to $D(X)$, a boundary edge once, and an outside edge zero times.

Coverage counts each internal or boundary edge once. Subtract one copy of every internal edge:
$|\mathrm{cov}(X)|=D(X)-|E[X]|.$

Additive guarantee

High degree loses only the internal-edge overcount

The largest degrees dominate the optimum's degree sum

Write $\mathrm{deg}(v_1)\ge \cdots \ge \mathrm{deg}(v_n)$. For an optimal set $O=\{v_{i_1},\dots ,v_{i_r}\}$ with $i_1<\cdots <i_r$ and $r\le h$, we have $i_j\ge j$, hence $\mathrm{deg}(v_{i_j})\le \mathrm{deg}(v_j)$. Therefore
$D(O)\le {\sum }_{j=1}^r\mathrm{deg}(v_j)\le D(A).$
Since $|\mathrm{cov}(O)|\le D(O)$, this gives $\mathrm{OPT}\le D(A)$.

Bound the overcount by vertex pairs

The $h$ selected vertices contain at most $\left(\genfrac{}{}{0ex}{}{h}{2}\right)$ internal edges: the graph is simple, so each unordered pair supports at most one edge. Consequently
$|\mathrm{cov}(A)|=D(A)-|E[A]|\ge D(A)-\left(\genfrac{}{}{0ex}{}{h}{2}\right)\ge \mathrm{OPT}-\left(\genfrac{}{}{0ex}{}{h}{2}\right).$

High-degree corollary

Large maximum degree makes the relative loss small

For $1\le k\le |V|$, $0<\epsilon <1$, and $\Delta >\left(\genfrac{}{}{0ex}{}{k}{2}\right)/\epsilon$, the algorithm is a $(1-\epsilon )$-approximation on instances satisfying this condition.

Proof

Compare the additive error with the optimum

A maximum-degree vertex alone covers $\Delta$ edges and is feasible because $k\ge 1$. Thus $\mathrm{OPT}\ge \Delta$, and
$\left(\genfrac{}{}{0ex}{}{k}{2}\right)<\epsilon \Delta \le \epsilon \mathrm{OPT}.$

Subtract the error bound

Applying the additive guarantee,
$|\mathrm{cov}(A)|\ge \mathrm{OPT}-\left(\genfrac{}{}{0ex}{}{k}{2}\right)>(1-\epsilon )\mathrm{OPT}.$

For $\epsilon \ge 1$, the requested non-strict approximation inequality is automatic from nonnegative coverage. This result does not say that the same near-optimal guarantee holds without the degree condition.