search_cover_random {gor}

Random vertex covers

Description

Random algorithm for vertex-cover.

Usage

search_cover_random(G, N, k, alpha = 1)

Arguments

G

Graph.

N

Number of random vertex set to try.

k

Cardinality of the random vertex sets generated by the algorithm.

alpha

Exponent of the probability distribution from which vertices are drawn: P(v) ~ d(v)^alpha.

Details

This routine performs N iterations of the simple procedure of selecting a random sample of size k on the vertex set of a graph and check if it is a vertex cover, counting successes and failures. The last cover found is returned, or an empty set if none is found.

Value

A list with four components: $set contains the subset of V(g) representing the cover and $size contains the number of vertices of the cover (it coincides with k). $found is the number of vertex covers found and $failed is the number of generated subset that were not vertex covers.

Author(s)

Cesar Asensio

See Also

is_cover checks if a vertex subset is a vertex cover, build_cover_greedy builds a cover using a greedy heuristic, build_cover_approx builds a cover using a 2-approximation algorithm, improve_cover_flip improves a cover using local search, 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

set.seed(1)
n <- 25
g <- sample_gnp(n, p=0.25)  # Random graph
X7 <- search_cover_random(g, 10000, 17, alpha = 3)
plot_cover(X7, g)
X7$found    # 21 (of 10000) covers of size 17

## Looking for a cover of size 16...
X8 <- search_cover_random(g, 10000, 16, alpha = 3)  # ...we don't find any!
plot_cover(X8, g)   # All edges uncovered
X8$found    # 0