maximiser MST (G [S]) sur tous les sous-graphes induits G [S] dans un graphe métrique

Ce problème a-t-il été étudié auparavant?

Étant donné un graphe métrique non orienté G (les longueurs d'arête satisfont l'inégalité du triangle), trouver un ensemble S de sommets tel que MST (G [S]) est maximisé, où MST (G [S]) est l'arbre couvrant minimum du sous-graphe induit par S. Ce problème a-t-il été étudié auparavant? Est-ce NP-difficile? Merci beaucoup.

Il est NP-complet par une réduction de la couverture des sommets.

Soit un graphe dans lequel une couverture optimale des sommets est difficile à trouver. Faire un nouveau graphique H avec deux fois plus de sommets, en attachant un nouveau sommet de degré un à chaque sommet de G . Transformez H en espace métrique en faisant la distance entre les sommets adjacents égale à 1 et la distance entre les sommets non adjacents égale à 2 . Pour cet espace métrique, le poids d'un arbre couvrant minimum d'un sous-graphique induit est égal au nombre de sommets plus le nombre de composants connectés du sous-graphique moins un.$G$$H$$G$$H$$1$$2$

Nous pouvons supposer que le sous-graphe avec le MST le plus lourd inclut tous les sommets de degré un, car l'ajout d'un de ces sommets à un sous-ensemble ne peut jamais diminuer le nombre de composants. Ainsi , les sommets qui ont été supprimés pour former le sous - graphe sont un sous - ensemble de . On peut supposer que ces sommets forment enlevés une couverture de sommet de G . Car, si un autre sous-graphique induit est formé en supprimant des sommets qui ne forment pas une couverture de sommet, et u v est un bord qui n'est pas couvert, alors la suppression de v conduit à un sous-graphique induit qui est au moins aussi bon: il en a un de moins sommet mais un autre composant connecté, créé par le sommet de degré un de H qui était attaché à v .$G$$G$$uv$$v$$H$$v$

Donc , le sous - graphe optimale de est formé en enlevant un couvercle de sommet de G . Un tel sous-graphe aura exactement n composants (un pour chaque sommet de degré un ajouté à H , seul ou connecté à un sommet de G ), et un nombre de sommets égal à 2 n - k où n = | V ( G ) | et k est la taille de la couverture. Ainsi, le poids de son MST sera de 3 n - k + 1 . Pour maximiser cela, nous devons minimiser k .$H$$G$$n$$H$$G$$2n-k$$n=|V(G)|$$k$$3n-k+1$$k$