Let ("S", "U") be an instance of the set cover problem with the universe "U" and the family of subsets "S" = {"S""i" : "i" ∈ "I"}; we assume that "U" and the index set "I" are disjoint. Construct a graph "G" = ("V", "E") as follows: the set of vertices is "V" = "I" ∪ "U", there is an edge {"i", "j"} ∈ "E" between each pair "i", "j" ∈ "I", and there is also an edge {"i", "u"} for each "i" ∈ "I" and "u" ∈ "S""i". That is, "G" is a split graph: "I" is a clique and "U" is an independent set.