co.combinatorics - Consensus clustering using set union

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}^pleft|P_icup 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 $kgeq 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).