Minimal Covering Set: System of Distinct Representatives

  • Context: Graduate 
  • Thread starter Thread starter WWGD
  • Start date Start date
  • Tags Tags
    Set
Click For Summary
SUMMARY

The discussion centers on the concept of a minimal covering set, specifically a System of Distinct Representatives (SDR), which aims to find the smallest subcollection of sets from a larger collection that contains every element in a specified subset. The problem is identified as a set cover problem, which is classified as NP-complete. The relationship between the number of sets (k) and the elements (j) is noted, emphasizing that a single element can belong to multiple sets.

PREREQUISITES
  • Understanding of set theory and its terminology
  • Familiarity with the concept of NP-completeness
  • Knowledge of combinatorial optimization techniques
  • Experience with algorithms related to set cover problems
NEXT STEPS
  • Research algorithms for solving the set cover problem, such as the Greedy Algorithm
  • Explore the implications of NP-completeness in computational theory
  • Study applications of Systems of Distinct Representatives in various fields
  • Learn about approximation algorithms for NP-complete problems
USEFUL FOR

Mathematicians, computer scientists, and algorithm developers interested in combinatorial optimization and set theory applications will benefit from this discussion.

WWGD
Science Advisor
Homework Helper
Messages
7,802
Reaction score
13,106
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

Similar threads

Undergrad "Minimal Cover" in Finite Collection of Sets?
  • · Replies 1 ·
Replies
1
Views
1K
Undergrad When does ## { n \choose k } ## represent set of lists?
  • · Replies 20 ·
Replies
20
Views
2K
Graduate How are Natural Numbers Constructed from the Class of All Finite Sets?
  • · Replies 12 ·
Replies
12
Views
3K
Graduate Is coutnable unions of finite sets an infinite set?
  • · Replies 3 ·
Replies
3
Views
7K
A proof that a union of compact spaces is compact
  • · Replies 12 ·
Replies
12
Views
3K
MHB An open cover is a collection of open sets whose union contains a given subset
  • · Replies 16 ·
Replies
16
Views
3K
Undergrad Enumerating a Large Ordinal: Can We Find a Limit to the Continuum?
  • · Replies 27 ·
Replies
27
Views
4K
Undergrad Tough lemma on locally finite refinement
  • · Replies 8 ·
Replies
8
Views
3K
Graduate Is the Number of Binary Sequences Countable or Uncountable?
  • · Replies 2 ·
Replies
2
Views
3K
High School Proving half of the Heine-Borel theorem
  • · Replies 3 ·
Replies
3
Views
2K