Najcięższy plansza podrzędna

Rozważ następujący problem.

Biorąc pod uwagę: Pełny wykres z rzeczywistymi nieujemnymi wagami na krawędziach.

Zadanie: znajdź płaski wykres podrzędny o maksymalnej masie. („Maksimum” wśród wszystkich możliwych płaskich wykresów podrzędnych.)

Uwaga: Podgraf maksymalnej wagi będzie triangulacją; jeśli cały wykres jest na wierzchołkach, będzie miał krawędzi.$n$$m=3n-6$

Pytanie: Jaki jest najlepszy dostępny algorytm dla tego problemu? Jaka jest złożoność czasu?

Jest to trudne dla NP nawet dla ważonych kompletnych wykresów. Aby uzyskać prosty algorytm, możesz obliczyć drzewo opinające o maksymalnej masie: zaneguj wagi krawędzi i uruchom algorytm Kruskala. Daje to współczynnik wydajności wynoszący 1/3 (drzewo opinające ma$n-1$ krawędzie i, jak zauważysz, maksymalny płaski wykres podrzędny może zawierać co najwyżej $3n-6$krawędzie). O ile mi wiadomo, algorytm w [1], który ma współczynnik wydajności co najmniej 25/72, a co najwyżej 5/12, nie został znacznie ulepszony (ale zobacz, o czym wspominają nowsze artykuły).

Dla kompletnych wykresów, których wagi krawędzi są zgodne z nierównością trójkąta, współczynnik wydajności algorytmu w [1] wynosi co najmniej 3/8. Myślę, że algorytm jest raczej zaangażowany i można go uruchomić$O(m^{3/2}n \log^6 n)$czas na ogólnych wykresach. Istnieje kilka prostszych wariantów, które autorzy przedstawiają również z różnymi współczynnikami wydajności i prawdopodobnie lepszymi czasami działania.

[1] Calinescu, G., Fernandes, CG, Karloff, H., & Zelikovsky, A. (2003). Nowy algorytm aproksymacyjny do wyszukiwania ciężkich podgrup płaskich. Al Algorytmica, 36 (2), 179-205.