Conjunto menor que cruza alguns conjuntos

Sejam conjuntos que possam ter elementos em comum. Estou à procura de um menor conjunto X tal que ∀ i $S_1,S_2,\ldots,S_n$$X$ .$\forall i,\,X\cap S_i \ne \emptyset$

Esse problema tem um nome? Ou reduz a algum problema conhecido?

No meu contexto, descreve os ciclos elementares de um componente fortemente conectado, e estou procurando um menor conjunto de vértices X que cruzam todos os ciclos.$S_1,\ldots,S_n$$X$

Seu primeiro problema é o problema transversal do hipergrafo (também conhecido como o problema HITTING SET ). O segundo problema é o problema FEEDBACK VERTEX SET . Ambos os problemas são NP- completos.

Se você quiser resolver instâncias reais, provavelmente gostará disso:

http://www.sagemath.org/doc/reference/sage/graphs/digraph.html#sage.graphs.digraph.DiGraph.feedback_vertex_set

Nathann

Se considerarmos S1, S2 ... Sn como uma sequência diferente e se precisarmos da subsequência mais longa que é comum nessas seqüências, esse tipo de problema é chamado de "Longest Common Subsequence (LCS)". Podemos alterar a condição para torná-la a menor subsequência comum que encontrará um único elemento do conjunto como a menor subsequência.

Por favor, veja exemplos de programação dinâmica, você obterá os detalhes ...