Fixed Parameter Tractability

Prowadząca

Karolina Sołtys

Opis

W tym roku opowiem o dość nowej i bardzo szybko rozwijającej się (również w Polsce) dziedzinie algorytmiki: algorytmach parametryzowanych, czy ogólniej - złożoności parametryzowanej (Fixed Parameter Tractability - FPT).

Niektóre naturalne problemy algorytmiczne (znajdowanie największej kliki w grafie, stwierdzanie, czy graf posiada cykl Hamiltona, i wiele, wiele innych) są NP-zupełne. Oznacza to, że prawdopodobnie nie da się ich rozwiązywać w czasie wielomianowym względem rozmiaru instancji (czyli w czasie $O(n^c)$, gdzie $n$ jest liczbą wierzchołków grafu, a $c$ - jakąś stałą). Okazuje się jednak, że problemy w tej klasie znacznie się między sobą różnią, jeśli ich złożoność będziemy rozpatrywać nie tylko jako funkcję rozmiaru wejścia, ale także jakiegoś parametru (często — rozmiaru szukanego rozwiązania). Przykładowo:

  • na pytanie, czy w grafie istnieje pokrycie wierzchołkowe rozmiaru co najwyżej $k$, umiemy odpowiedzieć w czasie $2^{O(k)} n^{O(1)}$,
  • najlepszy algorytm rozwiązujący problem "czy w grafie istnieje klika rozmiaru co najmniej $k$" działa w czasie $n^{O(k)}$, i wszyscy sądzą, że nie istnieje dla tego problemu algorytm działający w czasie $f(k)n^{O(1)}$.

Różnica polega na tym, że w pierwszym przypadku czas działania algorytmu jest wielomianowy ze względu na $n$, a stopień tego wielomianu nie zależy od $k$. Możemy więc w sensownym czasie szukać w grafie 1000-wierzchołkowym pokrycia wierzchołkowego rozmiaru 20, ale już na pewno nie ma sensu próbować szukać 20-wierzchołkowej kliki. Bardziej formalnie - problem (parametryzowany przez $k$) jest w FPT, jeśli umiemy go rozwiązywać w czasie $O(f(k) n^{O(1)})$, gdzie $f$ jest dowolną funkcją - intuicyjnie te problemy możemy szybko rozwiązywać dla małych parametrów, niezależnie od rozmiaru instancji.

Dziedzina ta ma duże znaczenie praktyczne, ale najbardziej pociąga mnie w niej fakt, że metody, którymi się w niej posługujemy, są ładne, naturalne, nietrudne i kombinatoryczne, a jednocześnie — bardzo skuteczne.

Program zajęć

  • podstawowe techniki:
    • kernelizacja,
    • ograniczone drzewa decyzyjne,
    • color coding,
    • interacyjna kompresja
  • szerokość drzewiasta (treewidth) i jej związki z FPT
  • FPT w grafach planarnych
  • (jeśli starczy czasu, i jeśli będzie to interesować słuchaczy) dlaczego niektóre problemy raczej nie są w FPT, czyli złożoność parametryzowana

Wymagania

Przyda się podstawowe obycie algorytmiczne i pojęcie złożoności czasowej algorytmu. Pomocna też będzie świadomość, że istnieją problemy trudne obliczeniowo (bez tego nasze rozważania mogą się wydać trochę wydumane); wystarczy znajomość klasy P (problemów obliczalnych w czasie wielomianowym), klasy NP (z grubsza — problemów, których "zgadnięte" rozwiązania umiemy szybko sprawdzać) i wiedza o istnieniu problemów NP-zupełnych (najtrudniejszych w klasie NP - tych problemów nie umiemy rozwiązywać w czasie wielomianowym). Jeśli jeszcze nie miałeś/miałaś z tym tematem styczności, to odradzam Wikipedię na początek (chyba, że masz ochotę zrobić po niej trwającego wiele godzin DFS-a); przeczytaj lepiej najpierw z tego krótkiego artykułu punkty "What is the P versus NP Problem?" i "Dealing with Hardness", a jeśli tematyka Cię zaciekawi, możesz sięgnąć po ten dłuższy i trochę bardziej formalny artykuł.

Zadania kwalifikacyjne

Pojawią się 24 maja. przed 30 maja. Pojawiły się 6 czerwca — przepraszam za opóźnienie i zachęcam do rozwiązywania :)

1. Opisz algorytm, który stwierdza, czy w danym grafie o $n$ wierzchołkach istnieje pokrycie wierzchołkowe rozmiaru co najwyżej $k$, w czasie $f(k) n^{O(1)}$, gdzie $f$ jest dowolną funkcją (nie musi być wielomianowa). Uwaga: to się daje łatwo zgooglać lub nawet znaleźć w odpowiednim dziale powyższego artykułu z wikipedii — ale zachęcam do samodzielnego zastanowienia się nad tym problemem; daje się go rozwiązać na wiele sposobów.

2. Opisz algorytm, który stwierdza, czy w danym grafie o $n$ wierzchołkach istnieje klika rozmiaru $n-k$, w czasie $f(k) n^{O(1)}$.

3. Opisz algorytm wielomianowy, znajdujący największy zbiór niezależny w danym drzewie. Rozwiąż ten problem również dla przypadku, gdy wierzchołkom drzewa przypisane są nieujemne wagi, a my szukamy zbioru niezależnego o jak największej wadze.

4. Rozważmy grę rozgrywaną na pewnym grafie $G$. W grze występuje złodziej dysponujący bardzo szybkim motorkiem, który pozwala mu przemieszczać się nieskończenie szybko, ale tylko po krawędziach grafu, oraz $k$ policjantów w helikopterach, którymi mogą wylądować w dowolnych wierzchołkach grafu. Jedna tura gry wygląda następująco:

  • część policjantów wzlatuje w powietrze i deklaruje, w jakich wierzchołkach grafu będą chcieli lądować w tej turze, pozostała część pozostaje na miejscach (oczywiście sytuacje, kiedy poruszają się wszyscy policjanci, lub kiedy wszyscy zostają w miejscu są jak najbardziej legalne)
  • złodziej, który podsłuchuje policyjną częstotliwość radiową, wie, gdzie wylądują policjanci; na swoim superszybkim motorku ucieka do dowolnie wybranego wierzchołka grafu, przy czym może poruszać się tylko po krawędziach i nie może przeskakiwać tych policjantów, którzy zostali na miejscach
  • policjanci lądują w wybranych przez siebie miejscach

Policjanci wygrywają, jeśli przy dowolnej strategii złodzieja uda im się go złapać (tzn. jakiś policjant znajdzie się w tym samym wierzchołku grafu, co złodziej), w przeciwnym razie wygrywa złodziej.

Znajdź najmniejszą liczbę policjantów $k$, która pozwala im wygrać ze złodziejem na:

  • a) drzewie
  • b) kracie $l$x$l$, czyli na grafie, którego wierzchołki odpowiadają parom $(i,j), i,j \in \{1,...,l\}$, a krawędź $( (a,b), (c,d) )$ występuje w grafie wtw., gdy $a=c$ i $|b-d| = 1$ lub gdy $b=d$ i $|a-c| = 1$.

Udowodnij, że znalezione przez Ciebie liczby policjantów są konieczne i wystarczające.

O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License