patternMinor
A variant of the set cover problem: Is that a known problem?
Viewed 0 times
problemvariantthethatknowncoverset
Problem
Can this problem be solved in poly time?
Input: $S_i \subset \{1,\cdots,n\}$ for $i=1,\cdots, n$.
Question: Is it possible to select an $a_i \in S_i$ for each $i=1,\cdots,n$, such that $\{a_1,\cdots,a_n\}=\{1,\cdots,n\}$?
Informally, the problem asks for selecting one element from each subset $S_i$ such that the selected elements cover the set $\{1, \cdots, n\}$.
Input: $S_i \subset \{1,\cdots,n\}$ for $i=1,\cdots, n$.
Question: Is it possible to select an $a_i \in S_i$ for each $i=1,\cdots,n$, such that $\{a_1,\cdots,a_n\}=\{1,\cdots,n\}$?
Informally, the problem asks for selecting one element from each subset $S_i$ such that the selected elements cover the set $\{1, \cdots, n\}$.
Solution
Hint: Form a bipartite graph which has the sets $S_1,\ldots,S_n$ on one side and the numbers $1,\ldots,n$ on the other. Connect $S_i$ to $a$ if $S_i$ contains $a$. You are looking for a perfect matching in this graph.
Context
StackExchange Computer Science Q#25931, answer score: 2
Revisions (0)
No revisions yet.