Mirkin Distance Minimization for Binary Strings is NP-hard

Summary

We consider a special variant of Clustering Aggregation, which asks for a binary string that minimizes the Mirkin distance to some input binary strings of equal length. The problem is known to be NP-hard under Turing reduction [1] . We strengthen this result by providing a polynomial-time many-one reduction. Unless ETH fails, no $2^{o(\hat{n})}\cdot |I'|^{O(1)}$ -time algorithm exists for our problem instances $I'$ with $\hat{n}$ being the length of the input strings.

Generally speaking, the Mirkin distance of two strings s and s’ counts the disagreements of s and s’ for each pair of columns.

$mirkin(s,s')=$ $|\{\{i,j\}\colon (s[i]=s[j] \wedge s'[i]\neq s'[j])$ $\vee (s[i])\neq s[j] \wedge s'[i]\neq s'[j]\}|$

====================================

[1] On the parameterized complexity of consensus clustering, by M. Dörnfelder and J. Guo and C. Komusiewicz and M. Weller.

Our paper can be found on arXiv.

Jiehua Chen