Remova os vértices até que nenhuma borda seja deixada

Question

Dado um gráfico não direcionado G (V, E), localize o número mínimo de vértices para remover para que o conjunto de borda do gráfico esteja vazio.

Em outras palavras: Se removermos um vértice, removemos esse vértice junto com todas as bordas conectadas a esse vértice.Encontre o número mínimo de vértices para remover para que não haja bordas deixadas em g após sua remoção.

Answer 1

Parece que você encontrou a resposta a si mesmo, você está descrevendo tampa do vértice , que em Muitas maneiras são muito semelhantes ao conjunto independente, ambos os problemas são np-completo .

A relação com o conjunto independente é que em um gráfico $ g= (v, e) $ , um conjunto $ S $ é uma tampa mínima de vértice se e somente se $ v \ setminus s $ é um conjunto independente máximo.

Se você souber que o conjunto independente é NP-completo, então segue que a tampa do vértice é NP-completa também.

Em outras palavras, você também está procurando um conjunto independente máximo.

tampa do vértice . Dado um gráfico $ g= (v, e) $ e um inteiro $ k $ existe Um conjunto $ s \ subseteq v $ de tamanho no máximo $ k $ tal que todas as bordas em $ g $ são incidentes a um vértice em $ S $ ?

conjunto independente . Dado um gráfico $ g= (v, e) $ e um inteiro $ k $ existe Um conjunto $ s \ subseteq v $ de tamanho pelo menos $ k $ tal que o induzido gráfico $ g [s] $ não tem bordas?