September 1st, 2011, 09:43 AM
Is this minimization problem NP-Complete ?
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.
Tags for this Thread
Click Here to Expand Forum to Full Width