# complexity theory – Polynomial kernelization for “Set coloring” problem

Given an universum $$U$$ and a system of its subsets $$Fsubseteq mathcal{P}(U)$$, given a $$kin mathbb{Z}_{geq 0}$$. The decision problem is to say whether there exists a $$2$$-coloring of $$U$$ s.t. atleast $$k$$ sets from $$F$$ contain elements of both colors.

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 $$xin U$$ s.t. there’s no $$Win F$$ s.t. $$xin W$$, then we can delete $$x$$ from U and work with a new instance. $$(F,Usetminus{x},k)$$.

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

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