Partition of a binary matrix into \(k\) (\(k \geq 3\)) exclusive row and column submatrices is difficult (Q1719430)

Summary: 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 \times 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 \geq 3\) by reduction from a biclustering problem in bipartite graphs.