2
$\begingroup$

This is a problem I met in my work. I thought about it for about two weeks, no result. I don't know whether it has been studied before by others?

Problem Description: Given an $m\times n$ matrix $M$ with entries valued 0 or 1. Let $r_i$ denote the $i^{th}$ row, $c_i$ denote the $i^{th}$ column and $t_{ij}$ denote the entry in the $i^{th}$ row and $j^{th}$ column. Find a $k \times n$ submatrix $A$ of $M$, such that in $A$ \begin{equation} \forall_{r_i}{ \exists_{c_a,c_b}{ \forall_{r_j \ne r_i}{\left( t_{ia} \ne t_{ib} \land t_{ja} = t_{jb} \right) } } }. \end{equation} $k$ is the parameter

The selected rows satisfy the following condition: For each row $r_i$, there exist two columns $c_a, c_b$, such that entries of the two columns at row $i$ are different, and at the remaining rows are the same.

Could someone give me any reference for it, if it has been studied before ? Thank you very much.

At first, I thought it was a special case of Minimum Test Set problem, however, it turns out not.

$\endgroup$
  • $\begingroup$ OK. It is not copied from some article, actually, I am asking for reference for this problem. It is copied from my draft. $\endgroup$ – Peng Zhang Sep 20 '11 at 15:12
1
$\begingroup$

This is not an answer, only an extended comment on a possible transformation of the problem (hope it is correct :-).

Each row can be "mapped" to a $n \times (n-1) / 2$ "extended" row. Each element of the extended row represents a pair of elements in the original row and is set to 1 if the two elements are different, set to 0 if the two elements are the same.

For example:

row_i = 10011  
        ^1100   (*)
         ^011   
          ^11
           ^0

extended_row_i = 1100 011 11 0

(*) note that in building the extended row, when the current bit (marked with ^)
is 0, the remaining bits are just copied and when the current bit is 1 the
remaining bits are inverted

We can extend each row and obtain an "extended" matrix. For example the matrix:

10011
01101
00011

Becomes:

1100 011 11 0
1101 010 10 1
0011 011 11 0

And the original problem reduces to find a submatrix of the "extended" matrix with exactly one 1 in each column.

$\endgroup$
  • $\begingroup$ Thank you very much for your kindness. I think the transformation is correct. Your transferred( extended ) matrix problem seems like NP-complete. So it does not justifies the original problem is NP-complete. If the extended matrix problem is in P, then the original problem got solved. Actually, I did a similar transformation before I ask, transferring a $n\times m$ input matrix to a $n \times (m-1)*m/2$ matrix, with each entry is a subset of indicies of rows. However, I cannot prove my transferred problem is NP-hard or polynomially solvable. $\endgroup$ – Peng Zhang Sep 21 '11 at 17:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.