# Is this minimization problem NP-Complete?

We are given an $n\times(n+k)$ matrix $A$, with entries in $GF(2)$, of the form $A=\begin{pmatrix}I_n & B\end{pmatrix}$, where $I_n$ is the $n\times n$ identity matrix, and $B$ has no "zero" rows or columns.

The problem is to partition the columns of $A$ into at most $m$ subsets, each of size at most $b$, such that the number of critical subsets 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 I am not able to understand from which problem we should try to reduce.

The elaborate problem definition/relevant discussion can be found here. I am defining it here in an abstract way.

-
This question was also posted at MO: mathoverflow.net/questions/73896/… – Martin Sleziak Aug 28 '11 at 14:07
Do you know that this is in NP? – Jyrki Lahtonen Aug 28 '11 at 14:52
@Jyrki: If we take the simplest decision problem for this optimization problem i.e. "Is there a configuration for which all the subsets will be non-critical" and if we are given a configuration, then we can check in polynomial time (by the rank test) whether for that configuration all the subsets become "non-critical". Here by a configuration I mean a sample distribution of the columns into m subsets. – aaaaaa Aug 28 '11 at 16:57
@Prasenjit: Ok. That decision problem is, indeed, in NP. – Jyrki Lahtonen Aug 28 '11 at 17:31
@Jyrki: I believe that from "bin packing" problem or "maximum independent set" problem, we can start to reduce – aaaaaa Aug 29 '11 at 3:24