improve_cover_flip {gor}

Improving a cover with local search

Description

Local search to improve a cover by using "neighboring" vertex subsets differing in just one element from the initial subset.

Usage

improve_cover_flip(G, X)

Arguments

G

A graph

X

A cover list with components $set, $size as returned by routines build_cover_greedy or build_cover_approx. X represents the cover to be improved

Details

Given some cover specified by a vertex subset X in a graph, this routine scans the neighboring subsets obtained from X by removing a vertex from X looking for a smaller cover. If such a cover is found, it replaces the starting cover and the search starts again. This iterative procedure continues until no smaller cover can be found. Of course, the resulting cover is only a local minimum.

Value

A list with two components: $set contains the subset of V(g) representing the cover and $size contains the number of vertices of the cover.

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

set.seed(1)
n <- 25
g <- sample_gnp(n, p=0.25)  # Random graph

X1 <- build_cover_greedy(g)
X1$size    # 17
plot_cover(X1, g)

X2 <- build_cover_approx(g)
X2$size    # 20
plot_cover(X2, g)

X3 <- improve_cover_flip(g, X1)
X3$size    # 17 : Not improved
plot_cover(X3,g)

X4 <- improve_cover_flip(g, X2)
X4$size    # 19 : It is improved by a single vertex
plot_cover(X4,g)

# Vertex subsets or n-1 elements are always vertex covers:
for (i in 1:25) {
   X3 <- improve_cover_flip(g, list(set = setdiff(1:25,i), size = 24))
   print(X3$size)
} # 19 18 18 18 18 18 17 20 19 17 17 18 18 18 17 19 20 19 19 17 19 19 19 19 19