Independent Set

Problem Definition

Independent Set is a subset of vertices in a undirected graph such that all the vertices in the set are not connected by edges (or called not adjacent). The IndependentSet problem is to find the independent set with maximum number of vertices.

Interfaces

To define an IndependentSet 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(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> IS = IndependentSet(graph)IndependentSet{SimpleGraph{Int64}, UnitWeight}(SimpleGraph{Int64}(4, [[2, 3], [1, 3], [1, 2, 4], [3]]), [1, 1, 1, 1])

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

julia> variables(IS)  # degrees of freedom4-element Vector{Int64}:
 1
 2
 3
 4
julia> flavors(IS)  # flavors of the vertices2-element Vector{Int64}:
 0
 1
julia> evaluate(IS, [1, 0, 0, 1]) # Positive sample: -(size) of an independent set-2
julia> evaluate(IS, [0, 1, 1, 0]) # Negative sample: 00
julia> findbest(IS, BruteForce())  # solve the problem with brute force2-element Vector{Vector{Int64}}:
 [1, 0, 0, 1]
 [0, 1, 0, 1]