0
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Steven
    Commented Sep 15, 2021 at 13:17
  • $\begingroup$ 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. $\endgroup$
    – George Polevoy
    Commented Sep 15, 2021 at 13:42

1 Answer 1

Reset to default
1
$\begingroup$

The problem is NP-hard by a straightforward reduction from the problem of finding a discriminating code in a bipartite graph.

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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