C,i≠j Definition
Given a collection of sets S1,…,Sm. Find the set C ⊆{1,…,m}, that contains the
largest amount of dices, such that Si ∩ Sj = ∅∀i,∀j C,i≠j
Polynomial Certifier
Given a collection of sets S1,…,Sm, and a target number k. Does there exists a set
C ⊆{1,…,m}, that contains at least k of dices, such that Si ∩ Sj = ∅∀i,∀j C,i≠j
Question:
C,i≠j to see if they intersect
with each other.
⋅ n2).Reduction from Independent Set from a simple case to general case
Given a graph G that contains Independent Set of size k, we produce the sets S1,S2,… as following: Since, in Independent Set, each vertex ”comes with” the set of all its incident edges, and if two vertices have an incident edge in common, they cannot be picked simultaneously. Having an incident edge in common means that the sets of incident edges intersect. Therefore, we generate a set Si for each vertex vi in G, so that the set contains exactly the edges e incident on vi. Finally, we set the size of Set Packing to be k as well.
From the construction, Set Packing of the example above would be S1 = {e1},S2 = {e2},S3 = {e3},S4 = {e4},S5 = {e5},S6 = {e6},S7 = {e1,e2,e3,e4,e5,e6}. So, the C = {1,2,3,4,5,6}.
Claim 4.12.2.1. Independent Set ≤p Set Packing (This construction of Independent
Set leads to is a special case of Set Packing)
IS is a Independent Set of size k in G if and only if C is a Set Packing of at
most k Si′s, such that Si ∩ Sj = ∅.
IS is a Independent Set of size k in G ⇒ C is a Set Packing of at most k Si′s, such that Si ∩ Sj = ∅.
Proof. Suppose G has an independent set of size at least k, call it IS. Construct
C by including exactly the Si with vi IS. Obviously, the size of C is equal
to the size of IS, k. Furthermore, since no two vertices in C can share an edge,
the sets Si we picked must be pairwise disjoint, so we have found a valid set
packing of at least k sets. __
C is a Set Packing of at most k Si′s, such that Si ∩Sj = ∅⇒ IS is a Independent Set of size k in G
Proof. Assume that we are given the new instance of set packing C of size at
least k. Then, we define a vertex set IS as consisting exactly of those vi for
which i C. The size of IS is the same as that of C, k. For any edge e, at most
one set Si with i C may contains e, so at most one node vi can be incident
on e. Thus, no two selected nodes are connected by an edge, and IS is in fact
an independent set of size at least k. __
Reduction from 3D-Matching from a simple case to general case
Given an instance of 3DM is < X,Y,Z,T >, where X, Y,Z are sets such that
|X| = |Y | = |Z| = n and T ⊆ X ×Y ×Z is a collection of triples of size n. Create an
instance of SET-PACKING < C,n > by setting C to be the collection of all the
triples in T. i.e, C = {{x,y,z}|(x,y,z) M}.
Claim 4.12.2.2. 3D-Matching ≤ p Set Packing (This construction of 3D-Matching
leads to is a special case of Set Packing)
< X,Y,Z,T > 3D-Matching if and only if < C,n > Set Packing
< X,Y,Z,T > 3D-Matching ⇒< C,n > Set Packing.
Proof. Suppose < X,Y,Z,T > 3D-Matching. By definition, this means there
is a set of triples M′⊆ M such that M’ covers each element in X∪Y ∪Z exactly
once. This means C′ = {{x,y,z}|
M′} is a collection of disjoint sets
(disjoint, since each element is covered at most once) of cardinality n (since there
are 3n elements to be covered and the cardinality of each set is 3). Therefore,
< C,n > Set Packing __
< C,n > Set Packing ⇒< X,Y,Z,T > 3D-Matching.
Proof. Suppose < C,n > Set Packing. This means, there is a sub-collection
C′ ⊆ C of disjoint sets such that |C′| = n. This means, M′ =
{(x,y,z)|{x,y,z} C′} covers each element in X ∪ Y ∪ Z at most once (since
the triples in M’ are disjoint). Also, since |C′| = n, M’ contains n (disjoint)
triples which, in turn, means that each element is covered exactly once. Thus,
3D-Matching holds. __
