maximizar MST (G [S]) sobre todas las subgrafías inducidas G [S] en un gráfico métrico

¿Se ha estudiado este problema antes?

Dado un gráfico métrico no dirigido G (las longitudes de los bordes satisfacen la desigualdad del triángulo), encuentre un conjunto S de vértices tal que MST (G [S]) se maximice, donde MST (G [S]) es el árbol de expansión mínimo del subgráfico inducido por S. ¿Se ha estudiado este problema antes? ¿Es NP-duro? Muchas gracias.

ds.algorithms graph-algorithms np-hardness approximation-algorithms jian
fuente

¿Existe un uso directo de este subgrafo en teoría o práctica?

Saeed

Si elimina la condición métrica, ¿es fácil demostrar que el problema es NP-duro?

Igor Shinkar

Tomar

para contener todos los vértices da una aproximación de

S

$S$

0.5

$0.5$

Neal Young

Respuestas:

Es NP-completo por una reducción de la cubierta del vértice.

$G$ $H$ $G$ $H$ $1$ $2$

$G$ $G$ $uv$ $v$ $H$ $v$

$H$ $G$ $n$ $H$ $G$ $2n-k$ $n=|V(G)|$ $k$ $3n-k+1$ $k$

David Eppstein
fuente