zmaksymalizować MST (G [S]) na wszystkich indukowanych podgraphach G [S] na wykresie metrycznym

Czy ten problem był już badany?

Biorąc pod uwagę metryczny niekierowany wykres G (długości krawędzi spełniają nierówność trójkąta), znajdź zestaw S wierzchołków, tak że MST (G [S]) jest zmaksymalizowany, gdzie MST (G [S]) jest minimalnym drzewem rozpinającym podgrafu wywołanym przez S. Czy ten problem był już badany? Czy to trudne NP? Wielkie dzięki.

Jest NP-kompletny poprzez redukcję z osłony wierzchołków.

Niech będzie wykresem, na którym trudno jest znaleźć optymalną osłonę wierzchołków. Złożyć nowy wykres z dwa razy więcej wierzchołków dołączając nowe stopień-on wierzchołek każdego wierzchołka . Zamień w przestrzeń metryczną, ustawiając odległość między sąsiednimi wierzchołkami równą i odległość między niesąsiadującymi wierzchołkami równą . W przypadku tej przestrzeni metrycznej waga minimalnego drzewa opinającego indukowanego podsgrafu jest równa liczbie wierzchołków plus liczba połączonych elementów podsgrafu minus jeden.$G$$H$$G$$H$$1$$2$

Możemy założyć, że podgraph z najcięższym MST obejmuje wszystkie wierzchołki stopnia 1, ponieważ dodanie jednego z tych wierzchołków do podzbioru nigdy nie może zmniejszyć liczby składników. Tak wierzchołki, które zostały usunięte w celu utworzenia podgrafu są podzbiorem . Możemy założyć, że te usunięte wierzchołki tworzą pokrywę wierzchołków . Bo jeśli powstaje jakiś inny indukowany podgraf, usuwając wierzchołki, które nie tworzą osłony wierzchołków, a jest krawędzią, która nie jest zakrywana, wówczas usunięcie prowadzi do indukowanego podgrafu, który jest co najmniej tak samo dobry: ma jeden mniej wierzchołka ale jeszcze jeden połączony komponent, utworzony przez wierzchołek stopnia pierwszego który został dołączony do .$G$$G$$uv$$v$$H$$v$

Tak więc optymalne subgraph z jest utworzona przez usunięcie pokrywy wierzchołek z . Taki podgraph będzie miał dokładnie składowych (jeden dla każdego wierzchołka stopnia jeden dodany do , sam z siebie lub połączony z wierzchołkiem ), i liczbę wierzchołków równą gdziea jest rozmiarem okładki. Zatem waga jego MST będzie wynosić . Aby to zmaksymalizować, musimy zminimalizować .$H$$G$$n$$H$$G$$2n-k$$n=|V(G)|$$k$$3n-k+1$$k$