I'm curious whether this problem is NP-hard: suppose you are given an arbitrary $m\times n$ 0-1 matrix (each element is either 0 or 1, for the simplicity of the problem), and any pair of rows (i.e. a 0-1 vector of dimension-$n$) are different (in other words, there are no repetitive rows). I'd like to select a minimum number of columns such that each row within these columns are different.

To make sure you understand it correctly, there is a firm lower bound, $\log_2m$, of the number of columns to be selected, but you don't know whether a solution of size $\log_2m$ exists. In addition, there must be a feasible solution of size $n$ since each row is different.

Is there an efficient algorithm for solving this? Or I need to solve it in a brute-forth way by checking every possible combinations of columns from $\log_2m$ to $n$?


Your problem is known to be NP-hard. See for instance

Vincent Froese, René van Bevern, Rolf Niedermeier, Manuel Sorge:
"Exploiting hidden structure in selecting dimensions that distinguish vectors."
Journal of Computer and System Sciences 82, pp 521-535 (2016).


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.