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 man - 1 krawędzie i, jak zauważysz, maksymalny płaski wykres podrzędny może zawierać co najwyżej 3 n - 6krawę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 (m3 / 2nlog6n )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.