Highest-Degree First Maximum Vertex Coverage Algorithm

Definition

Highest-Degree First Maximum Vertex Coverage Algorithm

For Maximum Vertex Coverage on with budget , select the vertices of highest original degree. Degrees are not recomputed after selections. The returned set satisfies

For and , if the maximum degree , then .

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 time. If , return the empty set. If , selecting all vertices is optimal.

Counting covered edges

Degree sum counts internal edges twice

For , let and let be the edges with both endpoints in . An internal edge contributes twice to , 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:

Additive guarantee

High degree loses only the internal-edge overcount

The largest degrees dominate the optimum's degree sum

Write . For an optimal set with and , we have , hence . Therefore

Since , this gives .

Bound the overcount by vertex pairs

The selected vertices contain at most internal edges: the graph is simple, so each unordered pair supports at most one edge. Consequently

High-degree corollary

Large maximum degree makes the relative loss small

For , , and , the algorithm is a -approximation on instances satisfying this condition.

Proof

Compare the additive error with the optimum

A maximum-degree vertex alone covers edges and is feasible because . Thus , and

Subtract the error bound

Applying the additive guarantee,

For , 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.