La preuve que la domination Ensemble est NP-Complet

ici est la question. Je me demande s'il est clair et efficace, la preuve:

Vertex Cover: entrée non orienté G, un entier k > 0. Est-il un sous-ensemble de
les sommets S, |S|<=k, qui couvre tous les bords?

Dominant Ensemble: entrée non orienté G, un entier k > 0. Est-il un sous-ensemble de
les sommets S, |S|<= k, qui domine tous les sommets?

Un sommet couvre l'incident bords et domine les voisins et lui-même.

En supposant que le CR est un PNJ, prouver que la DS est PNJ.

Cela peut vous aider en.wikipedia.org/wiki/...
Le dominant set problème est NP-Complet est de taille minimale-dominant, non seulement si un graphe a un dominant ou non. Pour prouver NPC son " oui " ou " pas de problème, donc, en utilisant tous les sommets d'un graphe connexe est un ensemble dominant par nature. Ce qui n'est pas le PNJ.

OriginalL'auteur SecureFish | 2011-03-15

  1. 8

    Il est très agréable, et bien connu de réduction: (Pour les graphiques uniquement)

    Donnée une instance (G,k) de Vertex Cover créer une instance de domination Set (H,k), où H vous prenez G et pour chaque arête (u,v) ajouter un sommet x relié à u et v.

    Abord se rendre compte que d'un Vertex Cover de G est un Ensemble Dominant de H (c'est clairement un DS de G et les nouveaux vertices sont également dominés). Donc, si G a un CR plus petit k, alors H est un DS plus petit k.

    Pour, à l'inverse, envisager D, un Ensemble Dominant de H.

    Avis que si l'un des nouveaux sommets est en D, nous pouvons le remplacer par l'un de ses deux voisins et toujours obtenir un Ensemble Dominant: c'est seuls voisins sont les deux sommets et ils sont également connectés - tout x peut être possible de le maîtriser est dominé par u ou v.

    Donc on peut supposer que D ne contient que des sommets de G. Maintenant, pour chaque arête (u,v) de G le nouveau sommet x est dominé par D, soit u ou v est en D. Mais cela signifie D est un Vertex Cover de G.

    Et là, nous avons: G a un Vertex Cover plus petit k si et seulement si H est un Ensemble Dominant plus petit k.

    OriginalL'auteur ian

  2. 0

    Prises à partir de :

    CMSC 651 Algorithmes Avancés , Professeur Samir Khuller

    La preuve que la domination Ensemble est NP-Complet

    OriginalL'auteur Stav Bodik

  3. -2

    Je pense que le deuxième problème n'est pas NP.
    Nous allons essayer de l'algorithme suivant.

    1. Get the original Graph
2. Run any algorithm which checks if a graph is connected or not.
3. mark all used edges of step 2
4. if the graph is connected then return the set of marked edges otherwise there is no such a set.

    Si j'ai bien compris votre problème, alors il n'est pas NP Complet.

    par manuel CLRS,il convient de PNJ, 🙁
    Le problème est en PNJ dans CLR?
    Voir en.wikipedia.org/wiki/Connectivity_(graph_theory) pour un gourmand de la connectivité de l'algorithme.
    vertex cover est PNJ en CLRS, chapitre 34
    après réflexion, je pense que peut-être que vous avez raison parce que j'ai une fois de résoudre le problème "trouver dominant de taille minimum défini à l'aide algorithme glouton" confondre

    OriginalL'auteur Luixv