Optimal partition according to partition cardinality
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.