W problemie Max-Cut szuka się podzbioru S wierzchołków danego prostego niekierowanego wykresu, tak że liczba krawędzi między S a dopełnieniem S jest tak duża, jak to możliwe.
Max-Cut jest kompletny APX na wykresach ograniczonego stopnia [PY91], i faktycznie APX-kompletny na wykresach sześciennych (tj. Grafach stopnia 3) [AK00].
Max-Cut jest NP-kompletny na grafach bez trójkątów o stopniu co najwyżej 3 [LY80] (bez trójkątów oznacza, że graf wejściowy nie zawiera K_3, kompletny wykres na 3 wierzchołkach, jako podgraf).
Pytanie: Czy Max-Cut APX jest kompletny na grafach bez trójkątów? (Uwaga: dozwolone są dowolne stopnie)
Dziękuję Ci.
AKTUALIZACJA: Znaleziono odpowiedź, ale nadal byłbym zainteresowany referencją do tego wyniku, jeśli taka istnieje.
Bibliografia:
[AK00] P. Alimonti i V. Kann: Niektóre wyniki kompletności APX dla grafów sześciennych. Teoria Comput. Sci. 237 (1-2): 123-134, 2000. doi: 10.1016 / S0304-3975 (98) 00158-3
[LY80] JM Lewis i M. Yannakakis: Problem usunięcia węzła dla właściwości dziedzicznych jest NP-Complete. J. Comput. Syst. Sci. 20 (2): 219–230, 1980. doi: 10.1016 / 0022-0000 (80) 90060-4
[PY91] CH Papadimitriou i M. Yannakakis: Klasy optymalizacji, aproksymacji i złożoności, J. Comput. System Sci., 43 (3): 425-440, 1991. doi: 10.1016 / 0022-0000 (91) 90023-X
Odpowiedzi:
Tak, poprzez redukcję z MaxCut do MaxCut bez trójkątów. Oto, co Wikipedia nazywa redukcją L.
Biorąc pod uwagę wystąpienie Max-Cut, skonstruuj 3-rozciągliwy , dzieląc każdą krawędź na trzy krawędzie. Następnie celu maksymalnego cięcia jest celu maksymalnego cięcia plus dwukrotna liczba krawędzi w . Ponieważ rozmiar maksymalnego cięcia zawsze wynosi co najmniej połowę liczby krawędzi, współczynnik błędów pogarsza się tylko o stały współczynnik.sol sol′ sol′ sol sol
źródło