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

11

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.

jian
fonte
Existe um uso direto deste subgráfico na teoria ou na prática?
Saeed
1
Se você remover a condição da métrica, é fácil provar que o problema é difícil para o NP?
Igor Shinkar
Tomar para conter todos os vértices fornece uma aproximação de . S0.5
Neal Young

Respostas:

3

É 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.GHGH12

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 .GGuvvvHv

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 + 1HGnHG2nkn=|V(G)|k3nk+1k

David Eppstein
fonte