patternMinor
Proof of sparsification lemma: What exactly does the $\pi$ operator do?
Viewed 0 times
thewhatoperatorlemmadoessparsificationexactlyproof
Problem
In their proof of the sparsification lemma, Impagliazzo et. al describe the following operator $\pi$:
For a familiy of sets $\mathcal{F}$, let $\pi(\mathcal{F}) \subseteq \mathcal{F}$ be the family of all sets $S$ in $\mathcal{F}$, such that no other set $S'$ in $\mathcal{F}$ is a proper subset of $S$.
I am trying to understand what this operator does. So far, I thought that it could be calculated by the following algorithm:
$$ \text{While}~\exists S_i, S_j \in \mathcal{F}: S_i \subset S_j \text{do} \\ \mathcal{F} \leftarrow \mathcal{F} \setminus S_i$$
By the rest of the proof seems to indicate that actually, one has to remove the superset:
$$ \text{While}~\exists S_i, S_j \in \mathcal{F}: S_i \subset S_j \text{do} \\ \mathcal{F} \leftarrow \mathcal{F} \setminus S_j$$
Which leads me to believe that I did not fully understand the description of the operator. What would be an algorithm to calculate that $\pi(F)$?
For a familiy of sets $\mathcal{F}$, let $\pi(\mathcal{F}) \subseteq \mathcal{F}$ be the family of all sets $S$ in $\mathcal{F}$, such that no other set $S'$ in $\mathcal{F}$ is a proper subset of $S$.
I am trying to understand what this operator does. So far, I thought that it could be calculated by the following algorithm:
$$ \text{While}~\exists S_i, S_j \in \mathcal{F}: S_i \subset S_j \text{do} \\ \mathcal{F} \leftarrow \mathcal{F} \setminus S_i$$
By the rest of the proof seems to indicate that actually, one has to remove the superset:
$$ \text{While}~\exists S_i, S_j \in \mathcal{F}: S_i \subset S_j \text{do} \\ \mathcal{F} \leftarrow \mathcal{F} \setminus S_j$$
Which leads me to believe that I did not fully understand the description of the operator. What would be an algorithm to calculate that $\pi(F)$?
Solution
From the definition you gave, the supersets have to be removed, as you want to keep only those sets for which there is no proper subset in $\mathcal{F}$.
For example:
In blue are the sets of $\mathcal{F}$ which don't have proper subsets in $\mathcal{F}$, in red are the ones who do. You want to keep the blue ones, by definition of $\pi$.
For example:
In blue are the sets of $\mathcal{F}$ which don't have proper subsets in $\mathcal{F}$, in red are the ones who do. You want to keep the blue ones, by definition of $\pi$.
Context
StackExchange Computer Science Q#113037, answer score: 4
Revisions (0)
No revisions yet.