Dominating Set

Problem Definition

Dominaing Set is a subset of vertices in a undirected graph such that all the vertices in the set are either in the dominating set or in its first-order neighborhood. The DominatingSet problem is to find the dominating set with minimum number of vertices.

Interfaces

To define a DominatingSet problem, we need to specify the graph and possibily the weights associated with vertices. The weights are set as unit by default in the current version and might be generalized to arbitrary positive weights in the following development.

julia> using ProblemReductions, Graphs
julia> graph = SimpleGraph(5){5, 0} undirected simple Int64 graph
julia> add_edge!(graph, 1, 2)true
julia> add_edge!(graph, 2, 3)true
julia> add_edge!(graph, 3, 4)true
julia> add_edge!(graph, 4, 5)true
julia> DS = DominatingSet(graph)DominatingSet{SimpleGraph{Int64}, UnitWeight}(SimpleGraph{Int64}(4, [[2], [1, 3], [2, 4], [3, 5], [4]]), [1, 1, 1, 1, 1])

Besides, the required functions, variables, flavors, and evaluate, and optional functions, findbest, are implemented for the Dominating Set problem.

julia> variables(DS)  # degrees of freedom5-element Vector{Int64}:
 1
 2
 3
 4
 5
julia> flavors(DS)  # flavors of the vertices2-element Vector{Int64}:
 0
 1
julia> evaluate(DS, [0, 1, 0, 1, 0]) # Positive sample: (size) of a dominating set2
julia> evaluate(DS, [0, 1, 1, 0, 0]) # Negative sample: number of vertices5
julia> findbest(DS, BruteForce())  # solve the problem with brute force3-element Vector{Vector{Int64}}:
 [1, 0, 0, 1, 0]
 [0, 1, 0, 1, 0]
 [0, 1, 0, 0, 1]