Independent Set -> Set Packing

In this tutorial, we will demonstrate how to reduce the [IndependentSet] (@ref) problem to the [SetPacking] (@ref) 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] (@ref) problem $(G, k)$. we aim to generate a corresponding [SetPacking] (@ref) 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] (@ref) 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] (@ref) 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] (@ref) 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] (@ref) problem either by extracting individual solutions via [extract_solution] (@ref) or extracting mutilple solutions via [extract_multiple_solutions] (@ref).

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] (@ref) problem.

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