Independent Set -> Set Packing

In this tutorial, we will demonstrate how to reduce the IndependentSet problem to the SetPacking problem and how to extract solutions back to the original problem.

Reduction Framework

Given an undirected graph $G=(V,E)$ and parameter $k$, we can have an instance of the IndependentSet problem $(G, k)$. we aim to generate a corresponding SetPacking instance $(U, S, k)$ (where $U$ is the union set, $S$ is the set of subsets and parameter $k$ is the required set packing size).

• Step-0: $k$ are the same;
• Step-1: Each edge $(u,v)\in E$ -> Create an element $x_{u,v}$ in $U$;
• Step-2: Each vertex $v \in V$ -> Create a subset $\{S_{u,v}|(u,v)\in E \}$.

It can be proven that:

• The instance $(G,k)$ is an yes-instance if and only if generated $(U,S,k)$ is an yes-instance;
• This transformation is within polynomial time.

Construct Reduction

We can firstly define a IndependentSet problem over a simple graph with $4$ vertices.

julia> using ProblemReductions, Graphs
julia> graph = SimpleGraph(4){4, 0} undirected simple Int64 graph
julia> for (i, j) in [(1, 2), (1, 3), (3, 4), (2, 3)]
           add_edge!(graph, i, j)
       end
julia> IS = IndependentSet(graph)IndependentSet{SimpleGraph{Int64}, Int64, UnitWeight}(SimpleGraph{Int64}(4, [[2, 3], [1, 3], [1, 2, 4], [3]]), [1, 1, 1, 1])

Then the reduction ReductionIndependentSetToSetPacking can be easily constructed by the reduceto function.

julia> result = reduceto(SetPacking, IS)ReductionIndependentSetToSetPacking{Int64}(SetPacking{Int64, Int64, UnitWeight}([1, 2, 3, 4], [[1, 2], [1, 3], [2, 3, 4], [4]], [1, 1, 1, 1]), [1, 2, 3, 4])

The target SetPacking problem can be accessed by the target field:

julia> SP = result.targetSetPacking{Int64, Int64, UnitWeight}([1, 2, 3, 4], [[1, 2], [1, 3], [2, 3, 4], [4]], [1, 1, 1, 1])

Extract Solutions

We can extract solutions from the target SetPacking problem either by extracting individual solutions via extract_solution or extracting mutilple solutions via extract_multiple_solutions.

julia> sol_SP = findbest(SP, BruteForce())2-element Vector{Vector{Int64}}:
 [1, 0, 0, 1]
 [0, 1, 0, 1]
julia> sol_extract_single = Set( unique( extract_solution.(Ref(result), sol_SP) ) )Set{Vector{Int64}} with 2 elements:
  [0, 1, 0, 1]
  [1, 0, 0, 1]
julia> sol_extract_mutilple = Set( extract_multiple_solutions(result, sol_SP) )Set{Vector{Int64}} with 2 elements:
  [0, 1, 0, 1]
  [1, 0, 0, 1]

We can find that these extracted solutions indeed match with the solutions to the original IndependentSet problem.

julia> sol_IS = findbest(IS, BruteForce())2-element Vector{Vector{Int64}}:
 [1, 0, 0, 1]
 [0, 1, 0, 1]