3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – D.W. Feb 16 '18 at 0:04
  • $\begingroup$ @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. $\endgroup$ – ale64bit Feb 16 '18 at 0:17
  • $\begingroup$ @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. $\endgroup$ – ale64bit Feb 16 '18 at 2:09
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.