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.

— Jian
źródło

Czy istnieje bezpośrednie zastosowanie tego subgrafu w teorii lub praktyce?

— Saeed,

Czy po usunięciu warunku metrycznego łatwo jest udowodnić, że problem jest trudny do rozwiązania?

— Igor Shinkar,

Przyjmowanie aby zawierało wszystkie wierzchołki, daje przybliżenie .

S

$S$

0.5

$0.5$

— Neal Young,

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$

— David Eppstein
źródło