# 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 =[I_n\ B]$, 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 (with minimum $m$), 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$.

By the phrase "minimum m" I mean that we want to partition using minimum subsets (at the max we can use $m$ subsets) without sacrificing the number of critical subsets. For example, suppose we are getting the optimum config (i.e number of critical subsets is minimum) with $m_1$ subsets ($m_1$ < $m$), then we need not use all the $m$ subsets. In real world these $m$ subsets are $m$ boxes. If I can get the optimum config with less than $m$ boxes, I need not use the remaining ones, they can be saved. Our aim is to solve the problem for any $n$,$k$,$m$,$b$ and any $A$ matrix with the mentioned properties i.e. we want to design a general polynomial time algorithm or prove that the general algorithm is NP-Complete.

The problem seems NP-Complete to me. It a special case of "set cover/maximum coverage problem" and that's why it is becoming very difficult to reduce from the general set cover/maximum coverage problem.

The elaborate problem definition/relevant discussion can be found at https://math.stackexchange.com/questions/57412/optimization-problem-for-a-parity-check-code. As we could not reach to any solution there, I am posting it here.

• It is not clear if it is in NP, how would you check if a partition has minimal number of critical subsets? – Kaveh Sep 1 '11 at 18:01
• the OP probably means NP-hard. – Suresh Venkat Sep 1 '11 at 19:36
• @Kaveh, why do you think it's not in NP? What about the standard transformation from an optimization problem to a decision problem? Parameterize the problem by a new constant $k$ and ask a yes/no question: "Is there a partition with $\le k$ critical subsets?" Since the number of subsets in a candidate-solution is a constant $m$, and we can check whether each of the subsets is a critical subset independently of rest, and since computing a matrix's rank is in P by Gaussian elimination, it seems this problem is in NP to me. – Daniel Apon Sep 1 '11 at 21:51
• @prasenjit, complexity is an asymptotic concept in the input size, it doesn't matter if it takes exponential time in $n+k$ if $n+k$ is bounded by a fixed constant, $\exp(n(n+k))$ will also be bounded by a fixed constant (independent of input size). – Kaveh Sep 2 '11 at 12:18
• I agree. It would be wise to add a concise statement of whether each variable is a constant or not to the OP. People will need to know what they're supposed to be analyzing without reading a dozen comments deep. – Daniel Apon Sep 2 '11 at 14:36