We are given an nx(n+k) matrix A, with entries in GF(2), of the form A=(In|B) where In is a nxn identity matrix where the matrix B has no "zero" rows or columns.

The problem is to partition the columns of A into atmost m subsets each of size atmost b such that the number of "critical subset"s is minimized, where a critical subset is a subset of the set of columns such that if we remove it from A the reduced matrix has rank less than n.

The problem seems to be NP-Complete to me but not able to understand from which problem we should try to reduce.

The elaborate problem definition/relevant discussion can be found at http://math.stackexchange.com/questions/57412/optimization-problem-for-a-parity-check-code. I am defining here in some abstract way. Also, I wanted to post it under NP-Complete tag.