Czy są znane wyniki na temat złożoności znalezienia separatora (dowolnej wielkości) spełniającego daną właściwość?
Wiem, że separator kliki jest łatwy do znalezienia (czas wielomianowy), a także wiem, że wiele artykułów rozważa problem znalezienia małych separatorów lub separatorów, które pozostawiają połączone komponenty wielkości co najwyżej ułamka wielkości oryginalnego wykresu. Ale co, jeśli potrzebny jest separator o innych właściwościach, powiedzmy, separator sześcienny, dwustronny lub 2-połączony? Łatwo jest również tworzyć właściwości, które trudno jest określić NP, dlatego interesujące byłoby rozróżnienie przypadków P i NPC.
Edycja: ktoś (który nie jest użytkownikiem tej witryny) właśnie powiedział mi, że problem jest wielomianowy, jeśli właściwość ma „wierzchołek uniwersalny”, a NP-zupełny, jeśli właściwość „indukuje niezależny zestaw” lub „indukuje pełny wykres dwustronny ".
źródło
Odpowiedzi:
Nasz artykuł:
http://arxiv.org/abs/1110.4765
pokazuje, że wiele z tych problemów można rozwiązać przy pomocy parametrów stałych, tzn. możemy w czasie zdecydować f (k) * O (n + m), czy istnieje separator st wielkości k. Dotyczy to na przykład problemu znalezienia podłączonego separatora st lub separatora, który jest niezależnym zestawem, lub separatora, który indukuje dwudzielny wykres. Nadchodzący artykuł dotyczy problemu znalezienia 2-podłączonego separatora st.
źródło
Trudno również ustalić, czy wykres ma wycięcie, które wywołuje wykres odłączony , czy wykres z dokładnie k składowymi dla wszystkich k> = 2 . Z drugiej strony połączone cięcie jest łatwe (to znaczy k = 1).
źródło