Optimal partition according to partition cardinality Given $N$ sets of integers $S_1, \ldots,S_N$ with $|S_i| \le K$.

We want to partition those sets such that the union of all sets in any given partition doesn't contain more than $K$ elements.

Can the minimum number of partitions be found in polynomial time? 
If so, how to know what other partition cost functions admit polynomial algorithms as well?
This problem is NPC; we can use it to decide whether there exist a $k$-clique.

Each edge $(u,v)$ is transformed into a set $S_{u,v}$, we put $u$ and $v$ into $S_{u,v}$, as well as $U$ globally unique elements. Set $K=\frac{k(k-1)}{2}U+k$ and $U=n^3$. Each share of the partition can contain $\frac{k(k-1)}{2}$ edges, if they form a $k$-clique; otherwise it can contain exactly $\frac{k(k-1)}{2}-1$ edges.

We add dummy edges to make sure the total number of edges has the form $C\cdot (\frac{k(k-1)}{2}-1)+1$. If there is no $k$-clique, we need $C+1$ shares, otherwise we need at most $C$ shares.