build_cover_approx {gor}

2-approximation algorithm for vertex cover

Description

Gavril's 2-approximation algorithm to build a vertex cover.

Usage

build_cover_approx(G)

Arguments

G

Graph

Details

This algorithm computes a maximal matching and takes the ends of the edges in the matching as a vertex cover. No edge is uncovered by this vertex subset, or the matching would not be maximal; therefore, the vertex set thus found is indeed a vertex cover.

Since no vertex can be incident to two edges of a matching M, at least |M| vertices are needed to cover the edges of the matching; thus, any vertex cover X should satisfy |X| >= |M|. Moreover, the vertices incident to the matching are always a vertex cover, which implies that, if X* is a vertex cover of minimum sise, |X*| <= 2|M|.

Value

A list with two components: $set contains the cover, $size contains the number of vertices of the cover.

Author(s)

Cesar Asensio

References

Korte, Vygen Combinatorial Optimization. Theory and Algorithms.

See Also

is_cover checks if a vertex subset is a vertex cover, build_cover_greedy builds a cover using a greedy heuristic, improve_cover_flip improves a cover using local search, search_cover_random looks for a random cover of fixed size, search_cover_ants looks for a random cover using a version of the ant-colony optimization heuristic, find_cover_BB finds covers using a branch-and-bound technique, plot_cover plots a cover.

Examples

## Example with known vertex cover
K25 <- make_full_graph(25)   # Cover of size 24
X0 <- build_cover_approx(K25)
X0$size  # 24
plot_cover(X0, K25)

## Vertex-cover of a random graph
set.seed(1)
n <- 25
g <- sample_gnp(n, p=0.25)
X2 <- build_cover_approx(g)
X2$size   # 20
plot_cover(X2, g)