I've already posted this question a while ago on MathOverflow, but to the best of my knowledge it is still open, so I'm reposting it here in the hope that someone might have heard of it.

Problem statement



1) What is the complexity of this problem (or of the corresponding decision problem)?


Previous work


Easy subcases

Here are some subcases I've found to be solvable in polynomial time:

  • the case $k=2$;

Moreover, when $k=3$, 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).


The problem is NP-hard. Proof is by reduction from the following problem:

Given a tripartite graph $G$ with $N$ vertices in each part, are there $N$ vertex-disjoint triangles in $G$?

Here's the reduction: given an instance $G$ of the above problem, let $A_1$, $A_2$, $A_3$ denote the set of vertices in each part of $G$, and $E_{ij}$ be the set of edges between $A_i$ and $A_j$. Also, number the vertices in each part by $1,\dotsc,N$.

We construct an instance of your problem with $n = |E(G)| + M$, where $M$ is a large number (say, $M = 10 |E(G)|$), and $p = N + 1$. The first $|E(G)|$ elements of $\{1,\dotsc,n\}$ correspond to the edges of $G$. The partition $P$ is defined as follows: $P_i$ for $i=1,\dotsc,N$ is the set of edges that have the $i$th vertex of $A_1$ as one of their endpoints. Clearly these sets are disjoint and their union is $E_{1,2} \cup E_{1,3}$. $P_{N+1}$ is everything else, i.e., $E_{2,3} \cup \{|E(G)| + 1, \dotsc, |E(G)| + M\}$. Similarly, we define $Q$ using $A_2$ instead of $A_1$, and $R$ using $A_3$ instead of $A_1$.

Now, we claim is that this instance has a solution of cost at most $3|E(G)| - 3N + M$ if and only if $G$ has $N$ disjoint triangles. To see this, first notice that since $M$ is large, any solution that has cost less than $2 M$ must map $P_{N+1}$ to $Q_{N+1}$ and $R_{N+1}$. This already accounts for $|E(G)| + M$ of the total cost, so we are left with $2 |E(G)| - 3 N$. Now, note that the intersection of each $P_i$ and each $Q_j$ is at most one (and similarly for $P_i$ and $R_k$, and also for $Q_j$ and $R_k$). So, the objective function is minimized if all these intersections can be 1 at the same time. This corresponds to $N$ disjoint triangles in $G$.


Your Answer

