Conjunto más pequeño que cruza algunos conjuntos dados

16

Sean conjuntos que pueden tener elementos en común. Estoy buscando un conjunto X más pequeño tal que i ,S1,S2,...,SnorteX .yo,XSyo

¿Este problema tiene un nombre? ¿O se reduce a algún problema conocido?

En mi contexto describo los ciclos elementales de un componente fuertemente conectado, y estoy buscando un conjunto más pequeño de vértices X que interseque todos los ciclos.S1,...,SnorteX

adl
fuente

Respuestas:

25

Su primer problema es el problema transversal del hipergrama (también conocido como el problema HITTING SET ). El segundo problema es el problema FEEDBACK VERTEX SET . Ambos problemas son NP- completos.

Yota Otachi
fuente
-3

Si consideramos S1, S2 ... Sn como secuencias diferentes y si necesitamos la subsecuencia más larga que es común en estas secuencias, este tipo de problema se denomina "Subsecuencia común más larga (LCS)". Podemos alterar la condición para convertirla en una subsecuencia común más pequeña que encontrará un elemento único del conjunto como una subsecuencia más pequeña.

Vea ejemplos de programación dinámica, obtendrá los detalles ...

Diplav
fuente
1
el tiempo será exponencial en norte
Sasho Nikolov