gor (version 2.0)

is_cover: Check vertex cover

Description

Check if some vertex subset of a graph covers all its edges.

Usage

is_cover(X, eG)

Value

Boolean: TRUE if X is a vertex cover of the graph represented by eG, FALSE otherwise.

Arguments

X

Vertex subset to check.

eG

Edgelist of the graph as returned by igraph::as_edgelist()

Author

Cesar Asensio

Details

The routine simply goes through the edge list of the graph to see if both ends of each edge are inside the vertex subset to be checked. When an edge with both ends outside X is encountered, the routine returns FALSE; otherwise, it returns TRUE.

See Also

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

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

X1 <- build_cover_greedy(g)
is_cover(X1$set, eg)   # TRUE
is_cover(c(1:10),eg)   # FALSE
plot_cover(list(set = 1:10, size = 10), g)  # See uncovered edges