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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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