Search code examples
algorithmlanguage-agnostic

How to find a minimal set of keys?

I have a set of keys K and a finite set S ⊂ K n of n-tuples of keys. Is there an efficient algorithm to find a bijective mapping f : S ↦ S' where S' ⊂ K k with k < n minimal that strips some of the keys, leaving the others untouched?

Solution

  • I'm afraid this is NP-complete.

    It is equivalent to set cover.

    Each of your keys allows you to distinguish certain pairs of elements (i.e. a set of edges). Your task is to select the smallest number of keys that allows you to distinguish every element - i.e. the smallest number of sets of edges that allows you to cover every edge.

    However, the wiki page shows an approximate solution based on integer programming that may give a useful solution in practice.

    Sketch of Proof

    Suppose we have a generic set cover problem:

    A,B,C
C,D
A,B,D

    where we need to find the smallest number of these sets to cover every element A,B,C,D.

    We construct a tuple for each letter A,B,C,D.

    The tuple has a unique number in position i if and only if set i contains the letter. Otherwise, they contain 0.

    There is also a zero tuple.

    This means that the tuples would look like:

    (0,0,0)  The zero tuple
(1,0,2)  The tuple for A (in sets 1 and 3)
(3,0,4)  The tuple for B (in sets 1 and 3)
(5,6,0)  The tuple for C (in sets 1 and 2)
(0,7,8)  The tuple for D (in sets 2 and 3)

    If you could solve your problem efficiently, you would then be able to use this mapping to solve set cover efficiently.