## Problem statement

Let $P$, $Q$ and $R$ be three partitions into $p$ nonempty parts (denoted by $P_h$'s, $Q_i$'s and $R_j$'s) of the set {$1,2,\ldots,n$}. Find two permutations $\pi$ and $\sigma$ that minimise $$\sum_{i=1}^p\left|P_i\cup Q_{\pi_i}\cup R_{\sigma_i}\right|.$$

## Questions

1) ~~Is there a polynomial time algorithm to solve this problem, or is it NP-hard to do so?~~ What is the complexity of this problem (or of the corresponding decision problem)?

2) If the problem is indeed solvable in polynomial time, does it remain true for any number $k\geq 4$ of partitions?

## Previous work

Berman, DasGupta, Kao and Wang study the same problem for $k$ partitions, but using pairwise $\Delta$'s instead of $\cup$ in the above sum. They prove that the problem is MAX-SNP-hard for $k=3$, even when each part has only two elements, by reducing MAX-CUT on cubic graphs to a special case of their problem, and give a $(2-2/k)$-approximation for any $k$. So far, I have not been able to find my problem in the literature, or to adapt their proof.

## Easy subcases

Here are some subcases I've found to be solvable in polynomial time, I'll update this section as I go until the question is resolved:

- the case $k=2$;
- the case $p=2$, for any $k$;
- when $k=3$: when no two parts are equal and all parts have size $2$, we have the lower bound $3p+1$ (I don't know if it's tight).