find_cover_BB {gor}

Branch-and-Bound algorithm for the Vertex-Cover problem

Description

This routine performs a version of the Branch-and-Bound algorithm for the VCP. It is an exact algorithm with exponential worst-case running time; therefore, it can be run only with a small number of vertices.

Usage

find_cover_BB(
  g,
  verb = TRUE,
  save.best.result = FALSE,
  filename.best.result = "best_result_find_cover_BB.Rdata",
  nu = gorder(g),
  X = c(),
  Xmin = c(),
  marks = rep("F", gorder(g)),
  call = 0
)

Arguments

g

Graph.

verb

Boolean: Should echo each newly found cover to the console? Defaults to TRUE.

save.best.result

Boolean: Should the algorithm save the result of the algorithm in a file? It defaults to FALSE. When save.best.result = TRUE, a file is created with the variable "Xbest" being the best result achieved by the algorithm before its termination.

filename.best.result

Name of the file created when save.best.result = TRUE. It defaults to "best_result_find_cover_BB.Rdata".

nu

Size of the best cover currently found.

X

Partial cover.

Xmin

Best cover found so far.

marks

Mark sequence storing the current state of the algorithm, see details.

call

Number of recursive calls performed by the algorithm.

Details

The algorithm traverses a binary tree in which each bifurcation represents if a vertex is included in or excluded from a partial cover. The leaves of the tree represent vertex subsets; the algorithm checks if at some point the partial cover cannot become a full cover because of too many uncovered edges with too few remaining vertices to decide. In this way, the exponential complexity is somewhat reduced. Furthermore, the vertices are considered in decreasing degree order, as in the greedy algorithm, so that some cover is found in the early steps of the algorithm and thus a good upper bound on the solution can be used to exclude more subsets from being explored. The full algorithm has been extracted from the reference below.

In this routine, the binary tree search is implemented by recursive calls (that is, a dynamic programming algorithm). Although the worst case time complexity is exponential (recall that the Minimum Vertex Cover Problem is NP-hard), the approach is fairly efficient for a branch-and-bound technique.

The tree node in which the algorithm is when it is called (by the user or by itself) is encoded in a sequence of vertex marks. Marks come in three flavors: "C" is assigned to "Covered" vertices, that is, already included in the partial cover. "U" is asigned to "Uncovered" vertices, that is, those excluded from the partial cover. Mark "F" is assigned to "Free" vertices, those not considered yet by the algorithm; one of them is considered in the actual function call, and the subtree under this vertex is explored before returning. This mark sequence starts and ends with all vertices marked "F", and is used only by the algorithm, which modifies and passes it on to succesive calls to itself.

When the verb argument is TRUE, the routine echoes to the console the newly found cover only if it is better than the last. This report includes the size, actual cover and number call of the routine.

The routine can drop the best cover found so far in a file so that the user can stop the run afterwards; this technique might be useful when the full run takes too much time to complete.

Value

A list with five components: $set contains the subset of V(g) representing the cover and $size contains the number of vertices of the cover. Component $call is the number of calls the algorithm did on itself. The remaining components are used to transfer the state of the algorithm in the search three from one call to the next; they are $partial, the partially constructed cover, and $marks, a sequence encoding the tree node in which the algorithm is when this function is called, see details.

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_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, plot_cover plots a cover.

Examples

set.seed(1)
g <- sample_gnp(25, p=0.25)        # Random graph
X7 <- find_cover_BB(g)
X7$size                            # Exact result: 16
X7$call                            # 108 recursive calls!
plot_cover(X7, g)

## Saving best result in a file (useful if the algorithm takes too
## long and should be interrupted by the user)
## It uses tempdir() to store the file
## The variable is called "Xbest"
find_cover_BB(g, save.best.result = TRUE, filename.best.result = "BestResult_BB.Rdata")