maximizar MST (G [S]) sobre todos os subgráficos induzidos G [S] em um gráfico métrico

Esse problema já foi estudado antes?

Dado um gráfico métrico não direcionado G (os comprimentos das arestas satisfazem a desigualdade do triângulo), encontre um conjunto S de vértices de modo que o MST (G [S]) seja maximizado, onde MST (G [S]) é a árvore de abrangência mínima do subgráfico induzida por S. Esse problema já foi estudado antes? É NP-difícil? Muito obrigado.

É NP-completo por uma redução da cobertura de vértice.

Seja um gráfico no qual é difícil encontrar uma cobertura ideal de vértice. Fazer um novo gráfico com o dobro de vértices, anexando um novo grau e um vértice de cada vértice de . Transforme em um espaço métrico, tornando a distância entre os vértices adjacentes igual a e a distância entre os vértices não adjacentes igual a . Para esse espaço métrico, o peso de uma árvore de abrangência mínima de um subgrafo induzido é igual ao número de vértices mais o número de componentes conectados do subgrafo menos um.$G$$H$$G$$H$$1$$2$

Podemos assumir que o subgrafo com o MST mais pesado inclui todos os vértices de grau um, porque a adição de um desses vértices a um subconjunto nunca pode diminuir o número de componentes. Assim, os vértices que foram removidos de modo a formar o subgráfico são um subconjunto de . Podemos supor também que estes vértices removidos formar uma cobertura de vértices de . Pois, se algum outro subgrafo induzido for formado removendo vértices que não formam uma cobertura de vértice e for uma aresta que não está coberta, a remoção de levará a um subgrafo induzido que seja pelo menos tão bom: ele tem menos um vértice mas mais um componente conectado, criado pelo vértice grau um de que foi anexado a .$G$$G$$uv$$v$$H$$v$

Assim, o subgráfico óptima de é formada através da remoção de uma cobertura de vértices de . Esse subgrafo terá exatamente componentes (um para cada grau - um vértice adicionado a , sozinho ou conectado a um vértice de ), e um número de vértices igual a quee é o tamanho da capa. Assim, o peso do seu MST seráG n H G 2 n - k n = | V ( L ) | k 3 n - k + $H$$G$$n$$H$$G$$2n-k$$n=|V(G)|$$k$$3n-k+1$$k$