Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
This question was also posted at MO:… – 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.