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.

  • 2
    This question was also posted at MO: http://mathoverflow.net/questions/73896/is-this-minimization-problem-np-complete2011-08-28
  • 0
    Do you know that this is in NP?2011-08-28
  • 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.2011-08-28
  • 1
    @Prasenjit: Ok. That decision problem is, indeed, in NP.2011-08-28
  • 0
    @Jyrki: I believe that from "bin packing" problem or "maximum independent set" problem, we can start to reduce2011-08-29
  • 0
    @Jyrki: If I refine problem like this: How much of the n+k columns can be covered using m subsets each of size atmost b then I think it is possible to formulate it as a maximum independent set problem. We will form a graph of n+k vertices where each vertex corresponds to one column but the definition of edges is not clear to me (this is the main problem I am trying to solve). Then the maximum independent set of this graph will give us the maximum subset (of the n+k columns) that can be covered.2011-08-30
  • 0
    @all: The reason I think that the problem is np-complete is that here without checking all possible combinations it is very difficult to find the optimum config. What do you think about the np-completeness of this problem?2011-08-30

0 Answers 0