Está encontrando a menor coleção de subconjuntos para que o número de elementos entre os subconjuntos seja <= o número de subconjuntos NP-hard?

Dada uma coleção de subconjuntos não vazios de $\{1,2,\ldots,N\}$ ($N$não corrigido), o problema é encontrar a menor coleção não vazia de subconjuntos, para que o número de elementos distintos que aparecem na união de subconjuntos seja menor ou igual ao número de subconjuntos escolhidos. Parece um problema difícil de NP, mas não posso provar. Qualquer ajuda?

Isso é muito longo para um comentário, mas não é realmente uma resposta completa.

Vamos reformular ligeiramente a configuração do problema como um gráfico bipartido $G$com $\{1,2,\ldots,N\} = X$ como um conjunto de vértices e a coleção de subconjuntos (por exemplo, $Y$) como o outro conjunto de vértices, com uma aresta entre $i \in X$ e $J \in Y$ iff $i \in J$. Para qualquer conjunto de vértices$W$ no $Y$, definir $N(W)$ ser o bairro de $W$ no $G$ - ou seja, o conjunto de todos os vértices em $X$ adjacentes a pelo menos um vértice em $W$.

Em seguida, o problema pede para encontrar um subconjunto mínimo $W \subseteq Y$ de tal modo que $|N(W)| \leq |W|$. No entanto, se mudarmos ligeiramente o critério para$|N(W)| \lt |W|$, descobrimos que esse subconjunto existe se, e somente se, não existir uma correspondência entre $X$ e $Y$ que cobre $Y$, pois é exatamente equivalente ao Teorema do Casamento de Hall .

Como essas correspondências são localizáveis ​​em tempo polinomial (por exemplo: via Hopcroft-Karp ), acho que essa versão do problema provavelmente deve ser relativamente fácil, mas eu teria que fazer mais algum trabalho para descobrir se e como os algoritmos padrão para bipartidos a correspondência expõe esses conjuntos deficientes e se conjuntos deficientes mínimos também podem ser obtidos facilmente. Além disso, não posso dizer imediatamente quanto mais difícil a versão original do problema (o que permite$|N(W)| = |W|$) é mais que esta versão modificada.

Você pode reduzir a partir de Clique. Crie um conjunto para cada vértice, cada um com n-1 elementos correspondentes aos n-1 outros vértices, com o elemento para v no conjunto u sendo igual ao elemento para u no conjunto v (mas não igual a qualquer outro elemento) se {u, v} é uma aresta e um elemento único, caso contrário. Em seguida, podemos escolher k strings que juntas contenham elementos k (nk) + k (k-1) / 2 se for somente se houver um clique do tamanho k. Em seguida, precisamos apenas adicionar o número correto de conjuntos de um elemento contendo o mesmo elemento, para que o número de conjuntos selecionados e elementos coletados seja o mesmo.