Rimuovi i vertici fino a quando non rimangono bordi
Dato un grafo non orientato G(V,E), trovare il numero minimo di vertici da rimuovere in modo che l'insieme degli spigoli del grafo diventi vuoto.
In altre parole: se rimuoviamo un vertice, rimuoviamo quel vertice insieme a tutti i bordi collegati a quel vertice. Trova il numero minimo di vertici da rimuovere in modo che non rimangano spigoli in G dopo la loro rimozione.
Risposte
Sembra che tu abbia trovato tu stesso la risposta, stai descrivendo Vertex Cover , che per molti versi è molto simile a Independent Set, entrambi i problemi sono NP-completi .
La relazione con Insiemi Indipendenti è quella in un grafico$G = (V,E)$, un set$S$è una copertura minima del vertice se e solo se$V \setminus S$è un insieme massimo indipendente.
Se sai che l'Insieme Indipendente è NP-completo, ne consegue che anche Vertex Cover è NP-completo.
In altre parole, stai anche cercando un insieme indipendente massimo.
Copertura del vertice . Dato un grafico$G = (V,E)$e un numero intero$k$, esiste un insieme$S \subseteq V$di dimensioni al massimo$k$tale che tutti i bordi dentro$G$ sono incidente ad un vertice in$S$?
Insieme indipendente . Dato un grafico$G = (V,E)$e un numero intero$k$, esiste un insieme$S \subseteq V$di dimensioni almeno$k$tale che il grafico indotto $G[S]$non ha spigoli?