Theoretical Computer Science
- co.combinatorics np-hardness
- Updated Thu, 16 Jun 2022 03:24:36 GMT
-
Consensus clustering using set union
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
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) 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 (http://dx.doi.org/10.1016/j.ipl.2007.06.008) study a similar 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:
- the case $k=2$;
- the case $p=2$, for any $k$;
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).
Solution
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$.
External Links
External links referenced by this document: