Partition of a Binary Matrix into k (k ≥ 3)‎ Exclusive Row and Column Submatrices Is Difficult

Abstract EN

A biclustering problem consists of objects and an attribute vector for each object.

Biclustering aims at finding a bicluster—a subset of objects that exhibit similar behavior across a subset of attributes, or vice versa.

Biclustering in matrices with binary entries (“0”/“1”) can be simplified into the problem of finding submatrices with entries of “1.” In this paper, we consider a variant of the biclustering problem: the k-submatrix partition of binary matrices problem.

The input of the problem contains an n×m matrix with entries (“0”/“1”) and a constant positive integer k.

The k-submatrix partition of binary matrices problem is to find exactly k submatrices with entries of “1” such that these k submatrices are pairwise row and column exclusive and each row (column) in the matrix occurs in exactly one of the k submatrices.

We discuss the complexity of the k-submatrix partition of binary matrices problem and show that the problem is NP-hard for any k≥3 by reduction from a biclustering problem in bipartite graphs.