Couverture de sommet minimum

Question

J'essaie d'obtenir une couverture de sommet pour un arbre "presque" avec 50 000 sommets. Le graphique est généré comme un arbre avec des arêtes aléatoires ajoutées en faisant "presque" un arbre.

J'ai utilisé la méthode d'approximation où vous mariez deux sommets, ajoutez-les à la couverture et supprimez-les du graphique, puis passez à un autre ensemble de sommets. Après cela, j'ai essayé de réduire le nombre de sommets en supprimant les sommets qui ont tous leurs voisins à l'intérieur de la couverture vertex.

Ma question est de savoir comment rendre la couverture de vertex encore plus petite? J'essaie d'aller aussi bas que possible.

Answer 1

Voici une idée, mais je ne sais pas si elle est une amélioration dans la pratique:

De https://en.wikipedia.org/wiki/Biconnected_component « Tout graphe connexe se décompose en un arbre de composants biconnexes appelé l'arbre bloc coupe du graphique. » De plus, vous pouvez calculer une telle décomposition en temps linéaire.

Je suggère que lorsque vous vous mariez et supprimez deux sommets, vous ne le faites que pour deux sommets dans le même composant biconnecté. Lorsque vous n'avez plus de sommets à fusionner, vous avez un ensemble d'arbres qui ne sont pas connectés les uns aux autres. Le problème de la couverture des sommets sur les arbres est traitable via la programmation dynamique: pour chaque nœud, calculer le coût de la meilleure réponse si ce nœud est ajouté à la couverture et si ce nœud n'est pas ajouté à la couverture. Vous pouvez calculer les réponses pour un nœud donné les meilleures réponses pour ses enfants. Une autre façon - pour autant que je sache mieux - serait de calculer l'arbre recouvrant minimum du graphe et d'utiliser la programmation dynamique pour calculer la meilleure couverture de sommet pour cet arbre, en négligeant les liens en dehors de l'arbre, enlever les liens couverts à partir du graphique, puis continuez en épousant les sommets comme avant.

Je pense que je préfère le spanning tree minimal. En produisant le spanning tree minimum, vous supprimez un petit nombre de liens. Un arbre avec N nœuds avait des liens N-1, donc même si vous ne récupérez pas l'arbre d'origine, vous en récupérez un avec autant de liens que lui. Une couverture de vertex pour le graphe complet est aussi une couverture de vertex pour l'arbre couvrant minimal donc si la réponse correcte pour le graphe complet a V sommets, il y a une réponse pour l'arbre recouvrant minimum avec au plus V sommets. S'il y avait k arêtes aléatoires ajoutées à l'arbre, il y a k arêtes (pas nécessairement les mêmes) qui doivent être ajoutées pour transformer le spanning-tree minimal en graphe complet. Vous pouvez certainement vous assurer que ces nouvelles arêtes sont recouvertes de k sommets au maximum. Donc, si la réponse optimale a V sommets, vous obtiendrez une réponse avec au plus V + k sommets.

Answer 2

La couverture de sommet minimum est un algorithme complet de NP, ce qui signifie que vous ne pouvez pas le résoudre dans un délai raisonnable, même pour quelque chose comme 100 sommets (pour ne pas mentionner 50k). Pour un arbre, il existe un algorithme glouton temporel polynomial qui est basé sur DFS, mais le fait que vous ayez des "bords aléatoires ajoutés" tout visser et rend cet algorithme inutile. , Affirme qu'il atteint le facteur 2 et affirme qu'aucun meilleur algorithme n'est connu, ce qui le rend peu probable que vous en trouviez un.

Answer 3

Voici une tentative de réponse exacte qui est traitable quand seulement un petit nombre de liens est ajouté, ou quand ils ne modifient pas beaucoup les distances inter-nœuds.

Recherchez un arbre recouvrant minimum et divisez les arêtes en «arêtes d'arbre» ​​et «arêtes ajoutées», où les arêtes d'arbre forment un arbre recouvrant minimal et les arêtes ajoutées n'ont pas été choisies pour cela. Ils peuvent ne pas être les bords réellement ajoutés pendant la construction, mais cela n'a pas d'importance.Tous les arbres sur N nœuds ont N-1 bords de sorte que nous avons le même nombre d'arêtes ajoutées que celles utilisées lors de la création, même si ce n'est pas les mêmes arêtes. Maintenant, prétendez que vous pouvez jeter un coup d'œil à la réponse à la fin du livre juste assez pour voir, pour un sommet de chaque bord ajouté, si ce sommet faisait partie de la meilleure couverture de sommet. Si c'était le cas, vous pouvez supprimer ce sommet et ses liens du problème. Sinon, l'autre vertex doit l'être pour que vous puissiez le supprimer et ses liens du problème.

Vous devez maintenant trouver une couverture de sommet minimum pour un arbre ou un certain nombre d'arbres déconnectés, et nous savons comment faire cela - voir mon autre réponse pour un peu plus de handwaving. Si vous ne pouvez pas jeter un coup d'œil à la fin du livre pour trouver une réponse, et s'il y a des bords ajoutés, essayez toutes les 2^réponses possibles qui se trouvaient à la fin du livre et trouvez le meilleur. Si vous avez de la chance, le lien ajouté A se trouve dans un sous-arbre différent du lien ajouté B. Dans ce cas, vous pouvez limiter les deux calculs nécessaires aux deux possibilités pour ajouter le lien A (ou B) aux calculs de programmation dynamique du sous-arbre concerné. vous avez seulement doublé le travail au lieu de le quadrupler. En général, si vos k arêtes ajoutées sont dans k sous-arbres différents qui n'interfèrent pas les uns avec les autres, le coût est multiplié par 2 au lieu de 2^k.