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|.$$


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).
  • 1
    $\begingroup$ Do you have any reason to expect it is even in NP? After all, even if we are given the right permutations, we'd have to verify the minimality, and this seems like it might be as hard as the whole problem. $\endgroup$ – Joel David Hamkins Jan 29 '10 at 14:50
  • $\begingroup$ Doesn't the fact that the decision version of this problem is in NP (since checking that the sum equals a given quantity is easy) imply that the optimisation version is also in NP (by repeatedly decreasing the prescribed quantity until we cannot find satisfying permutations anymore)? $\endgroup$ – Anthony Labarre Feb 1 '10 at 8:50
  • 4
    $\begingroup$ no, because if I present you with an answer, how do you verify its optimality efficiently ? $\endgroup$ – Suresh Venkat Feb 4 '10 at 9:45
  • $\begingroup$ Fair enough, there is clearly some confusion in my mind I need to resolve, thanks to both of you for pointing this out. I'm rephrasing question 1, and appending some cases I've solved. $\endgroup$ – Anthony Labarre Feb 5 '10 at 16:33
  • $\begingroup$ The statement you're thinking of is that if P=NP, then FP=FNP. That is, IF P=NP, then you can also solve your optimization problem efficiently. However, that does not make the problem in NP. The standard example of this is the traveling salesman problem. $\endgroup$ – aorq Feb 5 '10 at 18:47

Your Answer

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

Browse other questions tagged or ask your own question.