<p>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.</p>

<p>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$. </p>

<p>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$ &lt; $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. </p>

<p>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.</p>

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

CC BY-SA 3.0
2011-09-01T18:01:13.610Z
It is not clear if it is in NP, how would you check if a partition has minimal number of critical subsets?
Kaveh
CC BY-SA 3.0
2011-09-01T19:36:21.097Z
the OP probably means NP-hard.
Suresh Venkat
CC BY-SA 3.0
2011-09-01T21:51:13.543Z
@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
CC BY-SA 3.0
2011-09-01T23:27:56.620Z
@Daniel, you are correct (although it seems to me that m is not constant but in any case it is bounded by $n+k$, if $m$ and $b$ are constants then $n+k \leq mb$ and this is a finite language which has trivial complexity and can't be compelte).
Kaveh
CC BY-SA 3.0
2011-09-02T11:20:50.063Z
@Kaveh: Are you talking about any polynomial (in n+k) time algorithm for this problem? Then it will be better if you tell about the algorithm when you say it has "trivial complexity". I am not able to see any algo other than brute-force method. Meanwhile, I also agree with the explanation given by Daniel about the problem being in NP. The difficult part is to prove that the problem is NP-hard, I believe.
RIchard Williams
CC BY-SA 3.0
2011-09-02T11:51:35.553Z
@prasenjit: if $m$ and $b$ are fixed constants, this is a finite language and like all other finite languages it has trivial complexity (i.e. constant time).
Kaveh
CC BY-SA 3.0
2011-09-02T11:58:52.263Z
@all: For convenience I am posting the brute-force algo: Step1: First find all the parition of n+k objects into atmost m subsets. Step2: discard those partitons where some subset contains more than b objects. Step 3: Now, for each remaining partition calculate the number of critical subsets. Step 4: Output the parition where the number of critical subsets is minimized with minimum m. The Step 1 is problematic as time taken by it is exponential in n+k
RIchard Williams
CC BY-SA 3.0
2011-09-02T12:05:37.057Z
@Kaveh: How can it have constant time complexity? It is exponential in n+k if we use the brute force algorithm. I also want a minimum m with the number of critical subsets minimized.
RIchard Williams
CC BY-SA 3.0
2011-09-02T12:18:04.743Z
@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
CC BY-SA 3.0
2011-09-02T12:53:54.360Z
@Kaveh: My problem has four input variables: n,k,m,b. Why are you saying that m and b are constant? I want a general algorithm for any n,k,m,b.
RIchard Williams
CC BY-SA 3.0
2011-09-02T12:57:22.877Z
The problem's parameters appears to me to be: an integer $n$ and constants $k$, $m$, and $b$ which implies $n+k$ is unbounded. While a large part of the matrix is $I_n$, the right-hand side of the matrix $A$ (i.e. $B$) is a $n \times k$ matrix and its associated input data, which grows as $n$ grows: For every increase in the value of $n$ by 1, we get $1 \times k$ new "interesting" bits added to the matrix.
Daniel Apon
CC BY-SA 3.0
2011-09-02T12:58:54.340Z
Well, nevermind then. Didn't see prasenjit's last comment. The problem is more general than I initially interpreted.
Daniel Apon
CC BY-SA 3.0
2011-09-02T13:07:21.373Z
@ all: If the interpretation of the problem is not still clear you can check the elaborate problem definition from the link mentioned in the main question.
RIchard Williams
CC BY-SA 3.0
2011-09-02T13:33:05.760Z
@prasenjit, ?!! You should read comments more carefully before replying to them: ["it seems to me that m is not constant ..."](http://cstheory.stackexchange.com/questions/8050/is-this-minimization-problem-np-complete#comment-21703). I have been stating in my comments that "if they are constants ...", and you didn't object until now that you saw the problem with them being fixed constants! I think you should edit the question and clarify what are the inputs, stating it in a comment or directing people to another post is not enough. Btw, your last edit "(with minimum m)" is confusing.
Kaveh
CC BY-SA 3.0
2011-09-02T14:28:57.637Z
related post on [MO](http://mathoverflow.net/questions/72445/optimization-problem-related-to-parity-check-code)
Kaveh
CC BY-SA 3.0
2011-09-02T14:36:06.500Z
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
CC BY-SA 3.0
2011-09-02T18:24:42.220Z
@Kavey: Sorry, if my problem definition has created any confusion. Meanwhile, I have never used any word "constant" in my problem definition and that why I didn't object as the constant case is a trivial case. I have edited the problem definition. Hope the problem is clear now.
RIchard Williams
CC BY-SA 3.0
2011-09-02T21:53:38.477Z
@prasenjit, thanks for the clarification. :) (I was replying to [Daniel's comment](http://cstheory.stackexchange.com/questions/8050/is-this-minimization-problem-np-complete#comment-21701)).
Kaveh
CC BY-SA 3.0
2011-09-03T17:32:34.877Z
The general algo seems NP-Complete to me, but I am not sure from which problem I should try to reduce
RIchard Williams
CC BY-SA 3.0
2011-09-15T06:58:40.047Z
Should we declare this as an "open problem"?
RIchard Williams
<cc.complexity-theory><np-hardness><optimization><np><partition-problem>
Is this minimization problem NP-Complete?
RIchard Williams
# Is this minimization problem NP-Complete?

(Asked by: username_0 on 2011-09-01)

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.

**Tags:** cc.complexity-theory, np-hardness, optimization, np, partition-problem
> **Comments:**
> **username_1**: It is not clear if it is in NP, how would you check if a partition has minimal number of critical subsets?  
> **username_2**: the OP probably means NP-hard.  
> **username_3**: @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.  
> **username_1**: @Daniel, you are correct (although it seems to me that m is not constant but in any case it is bounded by $n+k$, if $m$ and $b$ are constants then $n+k \leq mb$ and this is a finite language which has trivial complexity and can't be compelte).  
> **username_0**: @Kaveh: Are you talking about any polynomial (in n+k) time algorithm for this problem? Then it will be better if you tell about the algorithm when you say it has "trivial complexity". I am not able to see any algo other than brute-force method. Meanwhile, I also agree with the explanation given by Daniel about the problem being in NP. The difficult part is to prove that the problem is NP-hard, I believe.  
> **username_1**: @prasenjit: if $m$ and $b$ are fixed constants, this is a finite language and like all other finite languages it has trivial complexity (i.e. constant time).  
> **username_0**: @all: For convenience I am posting the brute-force algo: Step1: First find all the parition of n+k objects into atmost m subsets. Step2: discard those partitons where some subset contains more than b objects. Step 3: Now, for each remaining partition calculate the number of critical subsets. Step 4: Output the parition where the number of critical subsets is minimized with minimum m. The Step 1 is problematic as time taken by it is exponential in n+k  
> **username_0**: @Kaveh: How can it have constant time complexity? It is exponential in n+k if we use the brute force algorithm. I also want a minimum m with the number of critical subsets minimized.  
> **username_1**: @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).  
> **username_0**: @Kaveh: My problem has four input variables: n,k,m,b. Why are you saying that m and b are constant? I want a general algorithm for any n,k,m,b.  
> **username_3**: The problem's parameters appears to me to be: an integer $n$ and constants $k$, $m$, and $b$ which implies $n+k$ is unbounded. While a large part of the matrix is $I_n$, the right-hand side of the matrix $A$ (i.e. $B$) is a $n \times k$ matrix and its associated input data, which grows as $n$ grows: For every increase in the value of $n$ by 1, we get $1 \times k$ new "interesting" bits added to the matrix.  
> **username_3**: Well, nevermind then. Didn't see prasenjit's last comment. The problem is more general than I initially interpreted.  
> **username_0**: @ all: If the interpretation of the problem is not still clear you can check the elaborate problem definition from the link mentioned in the main question.  
> **username_1**: @prasenjit, ?!! You should read comments more carefully before replying to them: ["it seems to me that m is not constant ..."](http://cstheory.stackexchange.com/questions/8050/is-this-minimization-problem-np-complete#comment-21703). I have been stating in my comments that "if they are constants ...", and you didn't object until now that you saw the problem with them being fixed constants! I think you should edit the question and clarify what are the inputs, stating it in a comment or directing people to another post is not enough. Btw, your last edit "(with minimum m)" is confusing.  
> **username_1**: related post on [MO](http://mathoverflow.net/questions/72445/optimization-problem-related-to-parity-check-code)  
> **username_3**: 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.  
> **username_0**: @Kavey: Sorry, if my problem definition has created any confusion. Meanwhile, I have never used any word "constant" in my problem definition and that why I didn't object as the constant case is a trivial case. I have edited the problem definition. Hope the problem is clear now.  
> **username_1**: @prasenjit, thanks for the clarification. :) (I was replying to [Daniel's comment](http://cstheory.stackexchange.com/questions/8050/is-this-minimization-problem-np-complete#comment-21701)).  
> **username_0**: The general algo seems NP-Complete to me, but I am not sure from which problem I should try to reduce  
> **username_0**: Should we declare this as an "open problem"?  

---

## 0 answers

