# 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?

• What's the context in which you encountered this problem? Can you credit the original source (e.g., the textbook, programming contest, etc.) where you saw this? – D.W. Feb 16 '18 at 0:04
• @D.W. The original context is explained here, where I originally asked the question: codeforces.com/blog/entry/57753?#comment-413869. In short, from trying to optimally split triangles to minimise draw calls in a 3D engine. An approximation suffices in practice, but an algorithm for the optimal solution caught my attention. – ale64bit Feb 16 '18 at 0:17
• @D.W. fair enough. I think I'm more interested in the theoretical complexity of the problem and edited the question accordingly (in practice, I have several options). I have a feeling this is reducible to clique cover, though: each set being a node of the graph and an edge is created if the union of both nodes contains no more than $K$ elements. Then a clique is a partition and we want to minimise the number of those. I probably have a flaw somewhere in that reasoning, though. – ale64bit Feb 16 '18 at 2:09

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.