Polynomial kernelization for Set Splitting

Question

In a set system $(U, F)$, $F\subseteq \mathcal{P}(U))$, we say that a function $f: U \to \{0, 1\}$ is a coloring of $(U, F)$. A set in $F$ is split by $f$ if $F$ receives both colors.

The Set Splitting problem is defined as follows:

Given an set system $(U, F)$ and an integer $k \in \mathbb{N}$, does there exists a coloring of $(U,F)$ that splits at least $k$ sets from $F$?

I wish to show that there exists kernel with $2k$ sets and $|U|\in O(k^2)$. So far I have these reduction rules:

Rule 1: If there is $x\in U$ s.t. there's no $W\in F$ s.t. $x\in W$, then we can delete $x$ from U and work with a new instance. $(F,U\setminus\{x\},k)$.

Rule 2: If $W\in F$ is a singleton, then we can remove it and work with $(F\setminus \{W\},U,K)$ because such $W$ will never contain two elements of different colors.

Rule 3: If $V\in F$ is s.t. $|V|\geq 2$ and $V\cap W$ is empty for each other $W\in F$, then we can color elements in $V$ somehow to satisfy the distinctness and we can lower $k$ by one.

Rule 4: From instance $(F,U,k)$ create instance $(F,U\cap \bigcup F,k)$, i.e. we are interested in coloring only the elements that are actually in some set $W\in F$.

Not really sure how to proceed from here. Any hints appreciated.

Answer 1

I understood the question as "select a subset of size $2k$ from $F$ such that (there exists coloring for $F$ $\iff$ there exists coloring for the subset)".

As you've said, you can remove all singleton and empty sets. The remaining sets have at least $2$ elements. You can show that any $2k$ such sets suffice.

Select $2k$ arbitrary sets with at least two elements. We assume that they have exactly $2$ elements (it's the worst case; the analysis is easy to modify for more than $2$ elements). We use the probabilistic method. For each element, we select the color randomly, and we compute the expected number of sets that have both colors. We show that the expected number of sets with both colors is $k$. Note that this is an expectation over all random colorings. Therefore, there must exist a coloring that gives the value greater or equal to the expectation, i.e. $\ge k$, as required.

Let $\{S_i\}_{i=1}^{2k}$ be the selected sets. For each set $S_i$ we introduce indicator variable $I_i$, which equals $1$ when the set $S_i$ has both colors, and $0$ otherwise. The expectation above equals $\mathbb E[\sum_{i=1}^{2k} I_i] = \sum_{i=1}^{2k} \mathbb E[I_i]$. For set $S_i = \{x_1, x_2\}$, with probability $\frac 12$, $x_1$ and $x_2$ have different colors. Therefore, $\mathbb E[I_i] = \frac 12$, and the required expectation is $2k \cdot \frac 12 = k$.