Vertex Covering

Problem Definition

A Vertex Cover is a subset of vertices in a graph, such that for an arbitrary edge, the subset includes at least one of the endpoints. The VertexCovering problem is to find the minimum vertex cover for a given graph.

Interfaces

To define a VertexCovering problem, we need to specify the graph and the weights associated with edges. The weights are by default set as unit.

julia> using ProblemReductions, Graphs
julia> graph = SimpleGraph(4){4, 0} undirected simple Int64 graph
julia> add_edge!(graph, 1, 2)true
julia> add_edge!(graph, 1, 3)true
julia> add_edge!(graph, 3, 4)true
julia> add_edge!(graph, 2, 3)true
julia> weights = [1, 3, 1, 4]4-element Vector{Int64}:
 1
 3
 1
 4
julia> VC= VertexCovering(graph, weights)VertexCovering{Vector{Int64}}(SimpleGraph{Int64}(4, [[2, 3], [1, 3], [1, 2, 4], [3]]), [1, 3, 1, 4])

The required functions, variables, evaluate, and optional functions: set_parameters are implemented for the vertex covering problem.

julia> variables(VC)  # degrees of freedom4-element Vector{Int64}:
 1
 2
 3
 4
julia> evaluate(VC, [1, 0, 0, 1]) # Negative sample9223372036854775807
julia> evaluate(VC, [0, 1, 1, 0]) # Positive sample4
julia> findbest(VC, BruteForce())  # solve the problem with brute force1-element Vector{Vector{Int64}}:
 [1, 0, 1, 0]
julia> VC02 = set_parameters(VC, [1, 2, 3, 4])  # set the weights of the subsetsVertexCovering{Vector{Int64}}(SimpleGraph{Int64}(4, [[2, 3], [1, 3], [1, 2, 4], [3]]), [1, 2, 3, 4])