Minimal Covering Set: System of Distinct Representatives

  • Context: Graduate 
  • Thread starter Thread starter WWGD
  • Start date Start date
  • Tags Tags
    Set
Join the discussion
Ask a follow-up here, or get your own question answered by working scientists, mathematicians and engineers — people, not an autocomplete.
Real named experts · corrections over time · the nuance an AI answer skips
1 reply · 1K views
Messages
7,828
Reaction score
13,156
Hi All,
Let ##s: \{s_1,s_2,...,s_j \}## be a collection of elements contained in the sets ##S:=\{S_1,S_2,...S_k \}## , no relation between ##j,k##; a given ##s_i## may be contained in one or more ##S_n##. I want to find a minimal "cover" for ##s##, i.e., the smallest subcollection of sets in ##S## that contains every element in ##s##. I think this is called an SDR : System of Distinct Representatives.
Is there a general formula dealing with this? Obviously, ##k## is an upper bound.
 
Physics news on Phys.org