Highest-Degree First Minimum Vertex Cover Algorithm

Definition

Highest-Degree First Minimum Vertex Cover Algorithm

Let $G=(V,E)$ 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 $G_0=G$ and the empty cover $C_0=\varnothing$, it repeatedly chooses a vertex of maximum degree in the remaining graph:

$$\begin{array}{rl}{v}_i& \in {\arg \max }_{v\in V(G_i)}{\mathrm{deg}}_{G_i}(v),\\ C_{i+1}& =C_i\cup \{v_i\},\\ G_{i+1}& =G_i-v_i.\end{array}$$

Here, $G_i-v_i$ deletes $v_i$ and every edge incident to it. The algorithm stops when $G_i$ has no edges and returns $C_i$. 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 $G=(V,E)$ be a finite undirected graph with $E\ne \varnothing$. The HDF minimum vertex cover algorithm returns a vertex cover $S_{\mathrm{HDF}}$ satisfying

$$|S_{\mathrm{HDF}}|\le (\ln |E|+1)\cdot \text{OPT},$$

where $\text{OPT}$ is the size of a minimum vertex cover, i.e.,

$$\text{OPT}=\underset{\begin{array}{c}S\subseteq V\\ S\text{ is a vertex cover}\end{array}}{\min }|S|.$$

Proof

Let $S^{\ast }$ be a minimum vertex cover. For each iteration $i$, let $E_i=E(G_i)$ and $S_i^{\ast }=S^{\ast }\cap V(G_i)$.

One iteration removes a fixed fraction

Assume $|E_i|>0$. Since $G_i$ is a subgraph of $G$, the restriction $S_i^{\ast }$ covers every edge of $G_i$. It need not be a minimum vertex cover of $G_i$.

Since $|E_i|>0$, the restricted cover is non-empty, so $1\le |S_i^{\ast }|\le |S^{\ast }|$. The degree bound follows through the incidence count, its average, and then its maximum:

$$\begin{array}{rl}& \underset{\text{cover incidences}}{\underbrace{\sum _{u\in S_i^{\ast }}{\mathrm{deg}}_{G_i}(u)}}\ge \underset{\text{remaining edges}}{\underbrace{|E_i|}},\underset{\text{cover size}}{\underbrace{1\le |S_i^{\ast }|\le |S^{\ast }|}}\\ & ⟹\underset{\text{average cover degree}}{\underbrace{\frac{1}{|S_i^{\ast }|}\sum _{u\in S_i^{\ast }}{\mathrm{deg}}_{G_i}(u)}}\ge \frac{|E_i|}{|S_i^{\ast }|}\ge \frac{|E_i|}{|S^{\ast }|}\\ & ⟹\underset{\text{largest cover degree}}{\underbrace{\underset{u\in S_i^{\ast }}{\max }{\mathrm{deg}}_{G_i}(u)}}\ge \frac{1}{|S_i^{\ast }|}\sum _{u\in S_i^{\ast }}{\mathrm{deg}}_{G_i}(u)\ge \frac{|E_i|}{|S^{\ast }|}.\end{array}$$

HDF deletes exactly ${\mathrm{deg}}_{G_i}(v_i)$ edges incident to its chosen vertex $v_i$; the preceding argument gives the following lower bound:

$$\begin{array}{rl}\underset{\text{edges actually removed}}{\underbrace{{\mathrm{deg}}_{G_i}(v_i)}}& \ge \underset{\text{guaranteed lower bound}}{\underbrace{\frac{|E_i|}{|S^{\ast }|}}},\\ \underset{\text{edges left}}{\underbrace{|E_{i+1}|}}& =\underset{\text{edges before}}{\underbrace{|E_i|}}-{\mathrm{deg}}_{G_i}(v_i)\\ & \le |E_i|-\frac{|E_i|}{|S^{\ast }|}=\left(1-\frac{1}{|S^{\ast }|}\right)|E_i|.\end{array}$$

The graph below realises equality in this step. The minimum cover is $S^{\ast }=\{a,b\}$. HDF may choose $a$, 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 $1-x\le e^{-x}$ yields

$$\underset{\text{edges after }i\text{ steps}}{\underbrace{|E_i|}}\le \underset{\text{repeated shrinkage}}{\underbrace{{\left(1-\frac{1}{|S^{\ast }|}\right)}^i|E|}}\le \underset{\text{exponential estimate}}{\underbrace{e^{-i/|S^{\ast }|}|E|}}.$$

Decay forces termination

Since $|E_t|$ is a non-negative integer, proving $|E_t|<1$ is enough to prove $|E_t|=0$. The exponential estimate guarantees this once

$$\begin{array}{rl}{e}^{-t/|S^{\ast }|}|E|<1& ⟺\ln |E|-\frac{t}{|S^{\ast }|}<0\\ & ⟺t>|S^{\ast }|\ln |E|.\end{array}$$

The smallest integer strictly larger than $|S^{\ast }|\ln |E|$ is

$$t=\lfloor |S^{\ast }|\ln |E|\rfloor +1.$$

For this choice,

$$\underset{\text{integer edge count}}{\underbrace{|E_t|}}\le e^{-t/|S^{\ast }|}|E|<\underset{\text{forces }|E_t|=0}{\underbrace{1}},$$

so $|E_t|=0$. Exactly one vertex is selected per non-terminal iteration, so

$$\begin{array}{rl}\underset{\text{chosen vertices}}{\underbrace{|S_{\mathrm{HDF}}|}}& \le \underset{\text{iterations}}{\underbrace{t}}\\ & =\lfloor |S^{\ast }|\ln |E|\rfloor +1\\ & \le |S^{\ast }|\ln |E|+1\\ & \le |S^{\ast }|(\ln |E|+1).\end{array}$$

Every edge leaves the residual edge set only when one of its endpoints is selected. Thus

$$\underset{\text{no edge remains}}{\underbrace{E_t=\varnothing }}⟹\underset{\text{every edge is covered}}{\underbrace{\forall e\in E:e\cap S_{\mathrm{HDF}}\ne \varnothing }},$$

so $S_{\mathrm{HDF}}$ is a vertex cover with the claimed bound.