2
$\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?

Improve this question
$\endgroup$
3
  • $\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, 2018 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$
    – user30584
    Feb 16, 2018 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$
    – user30584
    Feb 16, 2018 at 2:09

1 Answer 1

Reset to default
0
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.