Partition median problem

Definitions and mathematical statement

A partition of a finite set $S$ is a family of nonempty disjoint blocks whose union is $S$. Permit two elementary operations: merging two blocks, or splitting one block into two nonempty blocks in any way. Let $d(X,Y)$ be the minimum number of operations needed to transform partition $X$ into partition $Y$.

If $X\vee Y$ denotes their least common coarsening, obtained by transitively closing the relations of being in the same $X$-block or the same $Y$-block, then \[ d(X,Y)=|X|+|Y|-2|X\vee Y|, \] where $|X|$ counts blocks. Thus a proposed median's objective value can be computed from the explicitly supplied partitions.

Given $X_1,\ldots,X_k$, find in polynomial time a partition $Y$ of $S$ minimizing \[ \sum_{i=1}^k d(X_i,Y). \] Here $k$ is part of the input, and repeated input partitions are permitted and contribute repeatedly to the sum.

The minimizing partition may have any number of blocks and need not be one of the input partitions. Each split or merge costs one, independent of the sizes of its blocks. This distance therefore differs from counting elements moved between blocks, comparing pairwise co-membership disagreements, or matching block labels. Those alternative metrics define distinct median problems.

Short English statement

Can a median partition minimizing the total number of split and merge operations to given partitions be found in polynomial time?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000064 (AMR-029-0064), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Egres Open - List of open problems, Open-problem page: Partition median problem. Original source indexed by AMR-029-0064. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Partition median problem. Individual source page and explanatory remarks. https://lemon.cs.elte.hu/egres/open/Partition_median_problem.