show/hide this revision's text 4 Lower bound

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$: deciding whether there is a solution of size $3p$, when no two parts are equal and all parts have size $2$.2$, we have the lower bound $3p+1$ (I don't know if it's tight).
show/hide this revision's text 3 Mistake in previous work

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 $\cap$ \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$: deciding whether there is a solution of size $3p$, when no two parts are equal and all parts have size $2$.
show/hide this revision's text 2 Modified question 1, appended solved cases so we know what we can skip

Problem statement

Let $P$, $Q$ and $R$ be three partitions into $p$ nonempty parts (denoted by $P_i$'s, P_h$'s, $Q_j$'s Q_i$'s and $R_k$'s) 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$ k\geq 4$ of partitions(beyond $3$, since it is obviously solvable in polynomial time for $k=2$)??

Previous work

Berman, DasGupta, Kao and Wang study the same problem for $k$ partitions, but using $\cap$ 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$: deciding whether there is a solution of size $3p$, when no two parts are equal and all parts have size $2$.
show/hide this revision's text 1