Na wykresie niezależny zestaw jest podzbiorem wierzchołków, który nie zawiera krawędzi jako indukowanego podsgrafu. Problem znajdowania największych niezależnych zestawów na wykresie jest fundamentalnym zagadnieniem algorytmicznym i trudnym. Rozważmy bardziej ogólne pytanie dotyczące znalezienia (wielkości) największego zestawu wolnego od H na wykresie, gdzie wolny od H oznacza, że nie indukuje on podgrafu zawierającego kopię ustalonego wykresu H jako podtrafu indukowanego.
Czy dla ustalonego wykresu H przy danym wykresie wejściowym G trudno jest określić rozmiar największego zestawu wolnego od H w G?
Czy istnieje rozsądny sposób na zbudowanie „tabeli” wykresów H (lub klas H), aby wypełnić wpisy prawidłowymi odpowiedziami „tak” lub „nie” na powyższe pytanie? (Udawajmy, że „nie” = P, a nawet, że pozycja „nie” oznacza, że istnieje algorytm czasu policy w celu wygenerowania największego zestawu wolnego od H.)
W przeciwnym razie, czy istnieją nietrywialne klasy H, na które odpowiedź brzmi „tak”? ... nie?
Grzebałem wokoło, szukając dwóch zapytań o uogólnione / wolne od H liczby chromatyczne --- tu i tutaj --- kiedy przyszło mi do głowy, że (pozornie prostsze) „podwójne” zagadnienie wolnego od H analogu liczby niezależności może być również otwarty. Zdaję sobie sprawę z klasycznych prac dotyczących pokrewnego problemu z przypadkowymi grafami, por. np. Erdos, Suen i Winkler (1995) lub Bollobas i Thomason (2000), którzy są nadal bardzo aktywnymi badaniami. Być może więc jest już trochę pracy, której jeszcze nie widziałem, zajmującej się tym bardziej podstawowym pytaniem i której nie udało się znaleźć zgrubnego wyszukiwania w Internecie (stąd znacznik żądania referencyjnego).
Odpowiedzi:
[1] John M. Lewis, Mihalis Yannakakis: Problem usunięcia węzła dla dziedzicznych właściwości jest NP-Complete. J. Comput. Syst. Sci. 20 (2): 219–230 (1980)
źródło