Programowanie półcałkowitoliczbowe

W tym artykule zmierzymy się z problemem pokrycia wierzchołkowego (Vertex Cover). Poruszymy kilka kwestii na pograniczu optymalizacji liniowej, złożoności obliczeniowej oraz algorytmów parametryzowanych...

Większość Czytelników może znać ten problem z różnych źródeł (między innymi pojawiał się on już w Delcie przed laty), ale na wszelki wypadek na początek przypomnę definicję.

Definicja 1. Pokryciem wierzchołkowym grafu $=(V,E) G$ nazwiemy taki zbiór wierzchołków, że dla każdej krawędzi $(u,v) ∈E,$ występującej w grafie, przynajmniej jeden z wierzchołków $u,v$ należy do pokrycia.

Minimalne pokrycie wierzchołkowe to, oczywiście, takie, które zawiera najmniejszą możliwą liczbę wierzchołków.

Z teorii złożoności wiemy już, że nasz problem jest NP-zupełny. Znaczy to, że jeśli potrafilibyśmy go szybko rozwiązać, to poprzez pewne redukcje umielibyśmy również szybko rozwiązać wszystkie problemy z klasy NP. W tym przypadku przez "szybko" rozumiemy rozwiązanie działające w czasie wielomianowym, czyli $O(n$ dla pewnej stałej $c.$ Jedna ze słynniejszych hipotez w informatyce mówi, że $|P ≠NP,$ czyli że klasa problemów rozwiązywalnych w deterministycznym czasie wielomianowym jest mniejsza od tej rozpoznawanej w niedeterministycznym (czyli nie zachodzi $|NP ⊆ P,$ zawieranie $P ⊆ NP$ jest oczywiste). Przy założeniu, że hipoteza ta jest prawdziwa, problemów NP-zupełnych nie da się rozwiązywać w deterministycznym czasie wielomianowym.

Jak możemy znaleźć minimalne pokrycie wierzchołkowe?

Pierwszym pomysłem, jaki możemy mieć, jest przejrzenie wszystkich podzbiorów wierzchołków naszego grafu i wybranie takiego, który jest pokryciem wierzchołkowym i ma najmniejszy rozmiar. Takich podzbiorów jest $|2n$ (gdzie $|n$ to liczba wierzchołków w naszym grafie).

Możemy też się zabrać za to inaczej - okazuje się, że bardzo często w problemach kombinatorycznych z pomocą przychodzi programowanie liniowe.

Tak też jest i w naszym przypadku. Dla każdego wierzchołka $v$ w naszym grafie stworzymy zmienną całkowitą $x v$ oznaczającą, czy bierzemy $v$ do naszego pokrycia, czy też nie. Oczywiście, będziemy chcieli zminimalizować liczbę wziętych wierzchołków. Wymaganie co do pokrycia krawędzi wyrazimy, tworząc dla każdej krawędzi $(u,v)$ nierówność $xu + xv⩾ 1.$

Podsumowując powyższe, dostajemy następujący program liniowy całkowitoliczbowy:

Minimalizuj $Pv> V xv$ z zachowaniem warunków:

$xu + xv⩾ 1$ dla każdego $(u,v) ∈ E,$
$xw{∈0, 1}$ dla każdego $|w$

Potrafimy wyrazić więc problem NP-zupełny za pomocą ILP (Integer Linear Programming - programowanie całkowitoliczbowe). Oznacza to dokładnie, że pokazaliśmy w tym momencie NP-trudność problemu ILP. Tym samym nie oczekujemy, że dla ILP istnieje jakikolwiek algorytm działający w czasie wielomianowym.

Co się stanie, gdy zapomnimy o warunkach całkowitości dla naszych zmiennych?

Dostaniemy zwykły program liniowy, a przecież do rozwiązywania takiego istnieją już algorytmy wielomianowe! Pytanie, czy wyniki tego programu mogą się nam do czegoś przydać. Mogłoby się wydawać, że nie - przykładowo dla cyklu o 3 wierzchołkach optymalnym rozwiązaniem będzie dać $1 |x1 = x2 = x3 = 2,$ które nam za wiele nie mówi.

Okazuje się jednak, że ta forma programu liniowego może być dla nas wciąż użyteczna! W dziedzinie algorytmów parametryzowanych istnieje dział zwany kernelizacją. Wykorzystamy rozwiązanie naszego LP (Linear Programming) właśnie w procesie kernelizacji. Najpierw jednak może warto wspomnieć, co kryje się pod tajemniczymi hasłami użytymi powyżej.

W skrócie algorytmy parametryzowane to takie, w których wybieramy sobie parametr opisujący w pewien sposób instancję naszego problemu, a następnie względem tego parametru będziemy optymalizować prędkość działania naszego algorytmu. Parametry te mogą w najróżniejszy sposób opisywać problem, z którym się mierzymy. Oczywiście, podstawowym parametrem może być wielkość naszego problemu wejściowego, jednak dużo z takiego parametru raczej nie wyciągniemy. Sensowniejszym przykładem dla problemów grafowych może być, na przykład, maksymalny stopień wierzchołka w rozważanym grafie. W ogólności, do każdego problemu da się wymyślić dużo różnych parametrów, ale wybranie tego właściwego może okazać się sporym wyzwaniem.

Drugie tajemnicze słowo, czyli "kernelizacja", można przetłumaczyć jako znajdowanie jądra problemu - chcemy w szybkim czasie z jakiejś instancji problemu NP-zupełnego wydobyć jego najtrudniejszą obliczeniowo część. Dzięki temu bardzo często jesteśmy w stanie mocno ograniczyć rozmiary problemu, z którym się borykamy, co znacząco przyspieszy nasze obliczenia (zostanie nam dużo mniej zadań, które musimy przetworzyć w czasie wykładniczym). Aby rozjaśnić te pojęcia, za chwilę zilustrujemy je na przykładzie pokrycia wierzchołkowego.

Skupimy się tym razem na wersji decyzyjnej problemu pokrycia wierzchołkowego - czy dla danego grafu $|G$ istnieje pokrycie zawierające co najwyżej $|k$ wierzchołków. Jako parametru użyjemy rozmiaru poszukiwanego rozwiązania (czyli liczby wierzchołków $|k$ w pokryciu).

Używając rozwiązania naszego programu liniowego

Minimalizuj $Pv> V xv$ z zachowaniem warunku: $xu +xv ⩾ 1$ dla każdego $|(u,v)∈ E,$

podzielimy wierzchołki na $3$ zbiory:

$V0 = {v 0⩽ xv < 12}$
$-1 V1~2 = {v xv = 2}$
$V1 = {v 12 < xv ⩽1}.$

W tym momencie jasne się powinno stać, skąd w tytule wzięła się nazwa półcałkowite - przekształcamy rozwiązanie LP tak, żeby oprócz wartości całkowitych 0 i 1 osiągało ono trzecią wartość $1 |2.$ Okazuje się, że taka postać rozwiązania jest niezwykle użyteczna w znajdowaniu jądra. Pierwszym spostrzeżeniem, jakie możemy poczynić, jest to, że jeśli spojrzymy na którykolwiek wierzchołek $v ∈ V0,$ to musi mieć on sąsiada należącego do zbioru $|V1.$ Można jednak udowodnić dużo ciekawsze twierdzenie.

Twierdzenie 1 (Nemhausera-Trottera). Istnieje takie minimalne pokrycie wierzchołkowe $S$ w grafie G, że:

V1 ⊆S ⊆ V1∪ V1~2.

V0, — Rys. 2 U góry graf z odpowiednio zaznaczonymi kolorem wierzchołkami z $V , 0$ szaro z $V 1~2$ i czarno z $V . 1$ Na dole ten sam graf po wykonaniu na nim powyższej redukcji/

Dowód powyższego twierdzenia, oczywiście, pozostawiamy jako ćwiczenie dla Czytelnika. Skorzystamy z niego podczas następującej redukcji naszego problemu.

Mamy dany graf $G$ oraz liczbę $k$ (rozmiar pokrycia, który sprawdzamy). Jeśli $| Pv> V xv > k,$ to zwracamy odpowiedź nie. W przeciwnym przypadku zmniejszamy nasz graf poprzez wyrzucenie z niego wierzchołków należących do $|V0∪ V1$ oraz zmniejszenie wielkości poszukiwanego pokrycia w reszcie grafu do $k − V1 .$ Odpowiada to zachłannemu wzięciu wszystkich wierzchołków z $| V1$ do naszego rozwiązania.

Pozostało wykazać, że redukcja ta jest bezpieczna oraz sprawdzić jakiej wielkości jest jądro po jej zastosowaniu. Dalej przez $′′ | ,k) (G$ będę oznaczał instancję problemu, którą dostaniemy po zastosowaniu redukcji. Aby wykazać, że jest ona bezpieczna, wykażemy, że w $′,k′) (G$ możemy znaleźć rozwiązanie wtedy i tylko wtedy, gdy mogliśmy je znaleźć w $| ,k). (G$

Zacznijmy od wykazania, że krok stwierdzający odpowiedź $|nie$ jest poprawny. Wiadomo, że wynik LP jest zawsze niewiększy niż ILP. Z tego też powodu, jeśli wynik LP będzie większy niż $k,$ czyli stwierdzimy, że się nie da znaleźć rozwiązania w wersji bez warunku o całkowitości liczb, to tym bardziej z tym warunkiem by się nie dało.

Druga część bezpieczeństwa nie jest wiele trudniejsza do wykazania. Najpierw uzasadnijmy implikację

′′ ,k)tak(G,k)tak. (G

Jeśli $|S′$ to pokrycie grafu $′, G$ to na mocy wcześniejszej obserwacji, jeśli dołożymy wierzchołki z $V1∪ V0$ do grafu, a $|V1$ do pokrycia, to dostaniemy dokładnie pokrycie grafu $G$ co najwyżej o rozmiarze $|k.$

W przeciwną stronę: aby wykazać

,k)tak(G′,k′)tak, (G

korzystamy z twierdzenia Nemhausera-Trottera przytoczonego powyżej. Weźmiemy wtedy $S ′,$ będące częścią wspólną pokrycia $S$ dla całego grafu, oraz $V , 1~2$ aby otrzymać pokrycie dla $′ G$ o rozmiarze co najwyżej $′ |k.$

Ostatnią rzeczą jest wielkość jądra, które otrzymamy. Okazuje się, że rozmiar naszego nowego grafu $′ G$ będzie wynosił co najwyżej $|2k.$ Wystarczy zauważyć, że jest on tym samym, co liczba wierzchołków "połowicznych", co z kolei wynosi nie więcej niż podwojona wielkość rozwiązania naszego LP, które musi być mniejsze niż $k,$ gdyż w przeciwnym przypadku dostalibyśmy już odpowiedź nie. Powyższe zdanie matematycznie zapiszemy w postaci

′) = V1~2 =Q2xv⩽2Qxv⩽2k. V (G v>V1~2v>V

W ten oto prosty sposób udało nam się ograniczyć przestrzeń, którą musimy przejrzeć w czasie wykładniczym z $n$ do $|2k.$ Nie jest to, oczywiście, jedyna redukcja, którą można zastosować do tego problemu. Okazuje się, że sam proces redukcji można jeszcze przyspieszyć, sprowadzając nasze LP do problemu przepływu w grafie. Po więcej szczegółów na temat algorytmów parametryzowanych (jak i tego sprowadzenia) można zajrzeć do książki Parameterized Algorithms, która na użytek własny jest dostępna za darmo w internecie.

Oczywiście, nie jest to też jedyne zastosowanie programowania półcałkowitoliczbowego. W internecie można znaleźć pracę Half-integrality, LP-branching and FPT Algorithms, w której jest więcej szczegółów, jak i zastosowań tego rozwiązania. Serdecznie zachęcam do lektury!