Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
2  
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
1  
@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
1  
@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
show 2 more comments

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.