Let’s start from finding a minimum hitting set problem. Given a collection of sets $ U=\{\{S_1\},\{S_2\},\{S_3\},\{S_4\},\{S_5\},\{S_6\}\}=\{\{1, 2, 3\}, \{1, 3, 4\}, \{1, 4, 5\}, \{1, 2, 5\}, \{2, 3\}, \{4, 5\}\}$ ,

it is easy to know that a minimum hitting set is $ \{2,4\}$ .

I am thinking what this problem would be if the set $ S$ is also a collection of sets. For instance, given $ S_1=\{\{1,2,3\},\{3,4\},\{1,2\}\}$ ,

$ S_2=\{\{3\},\{3,5\},\{1,3\}\}$ ,

$ S_3=\{\{2,5\},\{4\},\{1,5\},\{1,10,6,7\}\}$ ,

then a minimum “hitting set” is $ \{3,4\}$ . That is because $ \{3,4\}$ only consists of two elements and hits every set (i.e., $ \{3,4\}\in S_1$ , $ \{3\}\subset \{3,4\}$ and $ \{4\}\subset \{3,4\}$ ).

Does anyone have an idea to solve this problem? Do you think it is a variant of hitting set problem? Is it an NP-hard problem?