Preuve d'exhaustivité NP d'un problème d'arbre couvrant

23

Je cherche des indices dans une question posée par mon moniteur.

Je viens donc de comprendre que ce problème de décision est NP-complete :

Dans un graphe , y a-t-il un arbre couvrant dans qui contient un ensemble exact de S = { x 1 , x 2 , , x n } comme feuilles. J'ai pensé que nous pouvons prouver qu'il est en réduisant le chemin hamiltonien vers ce problème de décision.G N P - c o m p l e t eggS={X1,X2,,Xn}NP-complete

Mais mon instructeur nous a également demandé en classe:

serait-il également si au lieu de "l'ensemble exact de ", nous faisons SNP-completeS

"inclure l'ensemble entier de et éventuellement d'autres feuilles" ou "sous-ensemble de "SSS

Je pense que "sous-ensemble de S" serait , mais je ne peux pas le prouver, je ne sais pas quel problème je peux le réduire à cela. Quant à "inclure l'ensemble de ..." je pense qu'il peut être résolu en temps polynomial. SNP-completeS

initialiser
la source
Pouvez-vous expliquer pourquoi vous pensez qu'une seule version peut être résolue en temps polynomial?
Raphael
@pad: "Mon instructeur a demandé en classe" n'est pas une tâche mais un puzzle. Voir également cette méta-discussion sur la balise devoirs.
Raphael

Réponses:

13

Bref, vos suppositions sont correctes. Aux fins de cette réponse, appelons les trois problèmes en question comme suit:

  • Version égalité: Etant donné un graphe et un ensemble S V , décider si G a un arbre couvrant T de telle sorte que l'ensemble de feuilles en T est égale à S . Comme vous l'avez dit, c'est NP-complet par une réduction du problème du chemin hamiltonien.g=(V,E)SVgTTS
  • Version Sous - ensemble: Compte tenu de et S comme ci - dessus, décider si G a un arbre couvrant T tel que l'ensemble des feuilles en T est un sous - ensemble de S .gSgTTS
  • Version Superset: Compte tenu de et S comme ci - dessus, décider si G a un arbre couvrant T tel que l'ensemble des feuilles en T est une surcouche de S .gSgTTS

Pour prouver que la version du sous-ensemble est NP-complète, vous pouvez toujours y réduire le problème de chemin Hamitonien. Essayez de modifier la preuve de l'exhaustivité NP de la version d'égalité.

Pour prouver que la version du surensemble peut être résolue en temps polynomial, essayez de trouver une condition nécessaire et suffisante pour qu'un tel arbre existe.T

Les deux versions (ainsi que certains autres problèmes concernant les arbres étendus) sont étudiées dans [SK05]. Mais je suppose que c'est mieux si vous essayez de résoudre les problèmes par vous-même avant de regarder les épreuves dans le papier, car regarder le papier peut être un gros spoiler. Malheureusement, j'avais regardé le document avant d'essayer de trouver un algorithme polynomial pour la version superset!


[SK05] Mohammad Sohel Rahman et Mohammad Kaykobad. Complexité de quelques problèmes intéressants sur les arbres enjambant. Lettres de traitement de l'information , 94 (2): 93–97, avril 2005. [ doi ] [ copie d'auteur ]

Tsuyoshi Ito
la source
Ravi de vous voir ici! Notez que nous avons également MathJax ici.
Raphael
1
Merci pour les conseils !! J'aimerais bien lire ceci avant d'aller en classe, il l'a gâté aujourd'hui haha. Si quelqu'un s'intéresse à l'algorithme polynomial de la version surensemble, un autre indice est la construction d'un nouveau graphique avec V \ L.
initialiser
0

Ces conseils n'étaient pas suffisants pour m'amener à une solution pour le problème du surensemble de S - bien que les conseils soient utiles et corrects. C'est ma pensée qui m'a permis de trouver une solution.

Que se passe-t-il si vous supprimez tous les sommets de S de G, (VS), puis trouvez un arbre couvrant T avec DFS? S'il y a des sommets encore non connectés dans G, disons v1; qu'est-ce que cela dit sur le rôle d'au moins un des sommets dans S qui a été supprimé? Qu'il se trouve dans le chemin vers v1 à partir d'un sommet qui est actuellement dans l'arbre couvrant. Ainsi, ce ne peut pas être une feuille (car les feuilles n'ont pas d'enfants). S'il n'y a pas de nœuds non connectés, cela signifie que chaque sommet de S peut être une feuille à condition qu'il ait un bord menant à l'arbre couvrant. Les sommets en S qui se connectent uniquement à d'autres sommets en S n'auront bien sûr pas de connexion à l'arbre couvrant et violeraient la condition. Il y a donc deux cas à vérifier:

  1. Si tous les nœuds qui ne sont pas dans S sont connectés après avoir supprimé S de G et trouvé un arbre couvrant
  2. Si chaque nœud de S peut être connecté directement à l'arbre couvrant.
DanGoodrick
la source