Definition
Highest-Degree First Minimum Vertex Cover Algorithm
Let
be a finite undirected graph. The highest-degree first algorithm is a greedy minimum vertex cover algorithm for the minimum vertex cover problem. It constructs a vertex cover without guaranteeing that the cover is minimum. Starting with the remaining subgraph
and the empty cover , it repeatedly chooses a vertex of maximum degree in the remaining graph: Here,
deletes and every edge incident to it. The algorithm stops when has no edges and returns . Any maximum-degree vertex may be chosen when there is a tie. The returned set is always a vertex cover, but it need not be a minimum vertex cover.
Logarithmic Upper Bound
Logarithmic Upper Bound
Let
be a finite undirected graph with . The HDF minimum vertex cover algorithm returns a vertex cover satisfying where
is the size of a minimum vertex cover, i.e.,
Proof
Let
be a minimum vertex cover. For each iteration , let and . One iteration removes a fixed fraction
Assume
. Since is a subgraph of , the restriction covers every edge of . It need not be a minimum vertex cover of . Since
, the restricted cover is non-empty, so . The degree bound follows through the incidence count, its average, and then its maximum: HDF deletes exactly
edges incident to its chosen vertex ; the preceding argument gives the following lower bound: The graph below realises equality in this step. The minimum cover is
. HDF may choose , whose three incident edges form exactly half of the six remaining edges. The remaining edge set decays geometrically
Iterating the one-step bound and using the exponential tangent inequality
yields Decay forces termination
Since
is a non-negative integer, proving is enough to prove . The exponential estimate guarantees this once The smallest integer strictly larger than
is For this choice,
so
. Exactly one vertex is selected per non-terminal iteration, so Every edge leaves the residual edge set only when one of its endpoints is selected. Thus
so
is a vertex cover with the claimed bound.