# Calculating minimal discriminator of a set of columns in a matrix with unique rows

Having a matrix $$M$$, with unique rows, how to calculate a minimal subset of colums $$D$$ such that every row is unique? Also, how to maximize the amount of unique rows, if the number of chosen columns is limited?

For example:

$$M$$ =

0 0 0 0 0 1
0 0 0 0 0 2
0 0 0 1 0 0
0 0 0 2 0 0


$$D$$ (columns {4, 6} from $$M$$) =

0 1
0 2
1 0
2 0


It seemed like a Bounded Knapsack Problem at first, but the weights of each item in knapsack depends on other items, so it's not a classical knapsack problem.

Is there a known solution for this problem?

• Do you want the discriminator to be minimal (i.e., no column of the discriminator can be removed while keeping rows unique) or minimum (i.e., there is no other discriminator with less columns)? In the former case it is easy to come up with a polynomial-time algorithm that computes a minimal discriminator, simply start with all the columns and iteratively try to remove each of of them. In the latter case the problem is NP-hard. See my answer. Sep 15, 2021 at 13:17
• I'm not sure if I can grasp the idea of a minimal. Seems like a greedy algorithm, which does not give the best possible solution, because keeping a certain column might allow for removal of many other columns. I think it could be used as an approximation which is fast to compute. Sep 15, 2021 at 13:42

Let if $$G=(I \cup A, E)$$ is the bipartite graph with $$I = \{i_1, \dots, i_n\}$$ and $$A=\{a_1, \dots, a_m\}$$, you can create a matrix $$M$$ with $$n$$ rows and $$n$$ columns. The entry on the $$j$$-th row and $$k$$-th column is $$1$$ if $$(i_j, a_k) \in E$$ and $$0$$ otherwise.
A minimum discriminator of $$M$$ induces discriminating code of $$G$$ having the same size, and vice-versa.