Jiehua Chen

Mirkin Distance Minimization for Binary Strings is NP-hard

Posted on by Jiehua Chen

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 -time algorithm exists for our problem instances with 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.

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

[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.