Set Gadgets:
Consider a set system in a universe \(\mathcal {U} = \lbrace 1, 2, \dots , \ell \rbrace \)  of \(\ell \)  elements. In \(G_{MDS}\)  there are \(T\)  vertices corresponding to sets \(S_{1}, S_{2}, \dots , S_{T} \subset \mathcal {U}\)  and another \(T\)  vertices corresponding to their complements \(\overline{S_{1}}, \overline{S_{2}}, \dots , \overline{S_{T}}\) . A vertex has the same name as the set it represents. There are \(2\ell \)  vertices \(\lbrace \alpha _{i}, \beta _{i}\rbrace _{i=1}^{\ell }\)  where each \(\alpha _{i}, \beta _{i}\)  corresponds to the element \(i\)  in the universe \(\mathcal {U}\) . There are edges between \(\alpha _{i}\)  and \(\beta _{i}\)  for each \(i \in \mathcal {U}\) . And there are membership edges between \(S_{j}\)  and \(\alpha _{i}\)  if \(i \in S_{j}\)  and between \(\overline{S_{j}}\)  and \(\beta _{i}\)  if \(i \notin S_{j}\) . We require a collection of sets \(S_{1}, \dots , S_{T}\)  that satisfy the following property which is used to prove hardness of approximation for set cover in different models [1]}, [2]}.
