Partition median problem
Let P be the set of partitions of a ground set S. We allow two operations on P: (1) splitting a class into two arbitrary classes and (2) joining two classes into one. For two partitions X and Y, let us define the distance d(X,Y) as the minimum number of such operations transforming X to Y. Given partitions [math]X_1,X_2,\ldots,X_k\in P[/math], find a partition [math]Y\in P[/math] in polyinomial time minimizing the total distance, [math]\sum_{i=1}^k d(X_i,Y).[/math]
Remarks
This is a question of Martin Loebl from the eighties. It is easy to see that d(X,Y) is a metric, and an optimal transformation sequence is if we first get the joint partition [math]X\vee Y[/math] from X by operation (2), and then transform it to Y using (1).
The special case when all partitions have at most one non-singleton class can be solved in polynomial time using submodular optimization methods. A further special case has a nice application. As observed by Loebl, the optimal attack problem by Cunningham[1] can be formulated as a partition median problem.
In a graph G=(V,E) with a nonnegative integer cost function c on the edges and a parameter [math]\lambda[/math], minimize [math]c(F)-\lambda \kappa(F)[/math] on the edge sets [math]F\subseteq E[/math].
Here [math]\kappa(F)[/math] is the number of connected components of G-F minus one. For this, we need suitable number of copies of partitions having exactly one nonsingleton class of size two (corresponding to the edges), and copies of the partition into singletons and of the partition into one single class.[2]
We may represent the partitions X and Y by arbitrary edge sets [math]F_X[/math] and [math]F_Y[/math] on S whose connected components are the classes of X and those of Y, respectively. Then the problem can be [math]d(X,Y)=2r(F_X\cup F_Y)-r(F_X)-r(F_Y)[/math], where r(F) denotes the rank function of the graphic matroid in the complete graph on S. Hence we may write the problem into the following equivalent form: given edge sets [math]F_1,F_2,\ldots,F_k[/math] on the ground set S, find an edge set H minimizing [math]2(\sum_{i=1}^k r(F_i\cup H))-kr(H).[/math]
This problem can also be asked for an arbitrary matroid M; we will refer it as the Matroid Median Problem. The complexity status of this problem is also unknown. One may formulate matroid theoretical generalizations, for example, it would be a consequence of the following.
Given a polymatroid function p on S, find a base B of M minimizing p(B).
Unfortunately, this problem can be shown to be NP-complete even for graphic matroids.
For fixed k, the Partition Median Problem is probably polynomial time solvable.
