6
$\begingroup$

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.

$\endgroup$
7
  • 2
    $\begingroup$ This question was also posted at MO: mathoverflow.net/questions/73896/… $\endgroup$
    – Martin Sleziak
    Aug 28, 2011 at 14:07
  • $\begingroup$ Do you know that this is in NP? $\endgroup$
    – Jyrki Lahtonen
    Aug 28, 2011 at 14:52
  • 1
    $\begingroup$ @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. $\endgroup$
    – aaaaaa
    Aug 28, 2011 at 16:57
  • 1
    $\begingroup$ @Prasenjit: Ok. That decision problem is, indeed, in NP. $\endgroup$
    – Jyrki Lahtonen
    Aug 28, 2011 at 17:31
  • $\begingroup$ @Jyrki: I believe that from "bin packing" problem or "maximum independent set" problem, we can start to reduce $\endgroup$
    – aaaaaa
    Aug 29, 2011 at 3:24

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .