Osłona wierzchołka - Vertex cover

Przykładowy wykres, który ma pokrycie wierzchołków składające się z 2 wierzchołków (na dole), ale żadnego z mniejszą liczbą.

W teorii wykres , A pokrywa wierzchołek (czasami pokrywa węzeł ) o wykresie to zbiór wierzchołków, które zawiera co najmniej jeden końcowy każdej krawędzi grafu . W informatyce problem znalezienia minimalnego pokrycia wierzchołków jest klasycznym problemem optymalizacji . Jest NP-trudny , więc nie może być rozwiązany za pomocą algorytmu wielomianowego, jeśli P ≠ NP. Co więcej, trudno to aproksymować - nie może być aproksymowane do współczynnika mniejszego niż 2, jeśli hipoteza o unikalnych grach jest prawdziwa. Z drugiej strony ma kilka prostych przybliżeń dwuczynnikowych. Jest to typowy przykład problemu optymalizacji NP-trudnej, który ma algorytm aproksymacyjny . Jego wersja decyzyjna , problem pokrycia wierzchołków , był jednym z 21 problemów NP-zupełnych Karpa i dlatego jest klasycznym problemem NP-zupełnym w teorii złożoności obliczeniowej . Co więcej, problem pokrycia wierzchołków jest rozwiązywalny za pomocą stałych parametrów i jest głównym problemem w sparametryzowanej teorii złożoności .

Pokrywa problemem minimalna wierzchołek może być przygotowana w postaci pół-integralną programu liniowego , którego podwójne liniowy program, to maksymalny błąd dopasowania .

Problemy z pokryciem wierzchołków zostały uogólnione na hipergrafy , zobacz Pokrycie wierzchołków w hipergrafach .

Definicja

Przykłady okładek wierzchołków

Przykłady minimalnych osłon wierzchołków

Formalnie pokrycie wierzchołków grafu nieskierowanego jest podzbiorem takiego , że jest to zbiór wierzchołków, w którym każda krawędź ma co najmniej jeden punkt końcowy w pokryciu wierzchołka . Mówi się, że taki zestaw pokrywa krawędzie . Górny rysunek pokazuje dwa przykłady osłon wierzchołków, z niektórymi osłonami wierzchołków zaznaczonymi na czerwono. ${\displaystyle V'}$${\ Displaystyle G = (V, E)}$${\ Displaystyle V}$${\ Displaystyle uv \ w e \ strzałka w prawo u \ w V '\ lub v \ w V '}$${\displaystyle V'}$${\displaystyle V'}$${\ Displaystyle G}$${\displaystyle V'}$

Pokrywa minimalna wierzchołek znajduje się pokrywa wierzchołek możliwie najmniejszej wielkości. Numer pokrycia wierzchołka to rozmiar minimalnego pokrycia wierzchołka, tj . . Dolny rysunek przedstawia przykłady minimalnych pokryć wierzchołków na poprzednich wykresach. ${\ Displaystyle \ tau}$${\ Displaystyle \ tau = | V' |}$

Przykłady

• Zbiór wszystkich wierzchołków to pokrycie wierzchołków.
• Punkty końcowe dowolnego maksymalnego dopasowania tworzą pokrycie wierzchołków.
• Zakończeniu dwustronnego wykres ma minimalne przykrycie wierzchołek wielkości .${\ Displaystyle K_ {m, n}}$${\ Displaystyle \ tau (K_ {m, n}) = \ min \ {\, m, n \, \}}$

Nieruchomości

• Zbiór wierzchołków jest pokryciem wierzchołka wtedy i tylko wtedy, gdy jego uzupełnieniem jest zbiór niezależny .
• W konsekwencji liczba wierzchołków grafu jest równa jego minimalnej liczbie pokrycia wierzchołków plus rozmiar maksymalnego niezależnego zbioru ( Gallai 1959).

Problem obliczeniowy

Problem minimalnego pokrycia wierzchołków to problem optymalizacyjny polegający na znalezieniu najmniejszego pokrycia wierzchołka w danym grafie.

INSTANCJA: Wykres ${\ Displaystyle G}$

WYJŚCIE: Najmniejsza liczba, taka, która ma pokrycie wierzchołka o rozmiarze .${\displaystyle k}$${\ Displaystyle G}$${\displaystyle k}$

Jeśli problem jest określony jako problem decyzyjny , nazywa się to problemem pokrycia wierzchołków :

INSTANCJA: Wykres i dodatnia liczba całkowita .${\ Displaystyle G}$${\displaystyle k}$

PYTANIE: Czy ma co najwyżej rozmiar pokrycia wierzchołków ?${\ Displaystyle G}$${\displaystyle k}$

Problem pokrycia wierzchołków jest problemem NP-zupełnym : był to jeden z 21 problemów NP-zupełnych Karpa . Jest często używany w teorii złożoności obliczeniowej jako punkt wyjścia dla dowodów NP-twardości .

Preparat ILP

Załóżmy, że każdy wierzchołek ma skojarzony koszt . (Ważony) problem minimalnego pokrycia wierzchołków można sformułować jako następujący całkowity program liniowy (ILP). ${\displaystyle c(v)\geq 0}$

zminimalizować	${\ Displaystyle \ textstyle \ suma _ {v \ w V} c (v) x_ {v}}$			(zminimalizuj całkowity koszt)
podlega	${\ Displaystyle x_ {u} + x_ {v} \ geq 1}$	dla wszystkich ${\ Displaystyle \ {u, v \} \ w E}$		(zakryj każdą krawędź wykresu),
	${\ Displaystyle x_ {v} \ w \ {0,1 \}}$	dla wszystkich . ${\ Displaystyle v \ w V}$		(każdy wierzchołek znajduje się w osłonie wierzchołka lub nie)

Ten ILP należy do bardziej ogólnej klasy ILP do pokrywania problemów . Szczelina integralność tego ILP jest , więc jego relaksacji (umożliwiając każda zmienna się w przedziale od 0 do 1, nie wymagając zmiennych tylko 0 lub 1) otrzymuje się czynnik algorytm aproksymacji do problemu Minimalna pokrywa wierzchołek. Co więcej, złagodzenie programowania liniowego tego ILP jest w połowie całkowe , to znaczy, istnieje optymalne rozwiązanie, dla którego każdy wpis wynosi 0, 1/2 lub 1. Z tego rozwiązania ułamkowego można uzyskać 2 przybliżone pokrycie wierzchołków wybierając podzbiór wierzchołków, których zmienne są różne od zera. ${\ Displaystyle 2}$${\ Displaystyle 2}$ ${\displaystyle x_{v}}$

Dokładna ocena

Decyzja wariant problemu tytułowej wierzchołek jest NP-zupełny , co oznacza, że jest mało prawdopodobne, że istnieje efektywny algorytm do rozwiązania go dokładnie dla dowolnych grafów. NP-zupełność można udowodnić redukcją z 3-spełnialności lub, jak to zrobił Karp, redukcją z problemu kliki . Pokrycie wierzchołków pozostaje NP-zupełne nawet w grafach sześciennych, a nawet w grafach planarnych o stopniu najwyżej 3.

W przypadku grafów dwudzielnych równoważność między pokryciem wierzchołków a maksymalnym dopasowaniem opisana przez twierdzenie Kőniga umożliwia rozwiązanie problemu dwudzielnego pokrycia wierzchołków w czasie wielomianowym .

W przypadku grafów drzewa algorytm znajduje minimalne pokrycie wierzchołka w czasie wielomianowym, znajdując pierwszy liść w drzewie i dodając jego rodzica do minimalnego pokrycia wierzchołka, a następnie usuwając liść i rodzica oraz wszystkie powiązane krawędzie i kontynuując wielokrotnie, aż żadne krawędzie nie pozostaną w drzewo.

Zdolność do wykonywania stałych parametrów

Wyczerpująca wyszukiwania algorytm może rozwiązać ten problem w czasie 2 ^K n ^{O (1)} , gdzie k jest wielkość osłony wierzchołka. Pokrycie wierzchołków jest więc kurczliwe i jeśli interesuje nas tylko małe k , możemy rozwiązać problem w czasie wielomianowym . Jedna z technik algorytmicznych, która tutaj działa, nazywa się algorytmem ograniczonego drzewa poszukiwań , a jej ideą jest wielokrotne wybieranie jakiegoś wierzchołka i rekurencyjnej gałęzi, z dwoma przypadkami na każdym kroku: umieść bieżący wierzchołek lub wszystkich jego sąsiadów w okładce wierzchołka. Algorytm rozwiązywania pokrycia wierzchołków, który osiąga najlepszą asymptotyczną zależność od parametru, działa w czasie . Wartość klam tego ograniczenia czasowego (oszacowanie największej wartości parametru, którą można rozwiązać w rozsądnym czasie) wynosi około 190. Oznacza to, że o ile nie można znaleźć dodatkowych ulepszeń algorytmicznych, algorytm ten jest odpowiedni tylko dla przypadków, których wierzchołek numer okładki wynosi 190 lub mniej. Przy rozsądnych założeniach teorii złożoności, a mianowicie hipotezie czasu wykładniczego , czasu przebiegu nie można poprawić do 2 ^{o ( k )} , nawet jeśli jest . ${\ Displaystyle O (1,2738 ^ {k} + (k \ cdot n))}$${\ Displaystyle n}$${\ Displaystyle O (k)}$

Jednak w przypadku grafów planarnych i ogólniej, w przypadku grafów wykluczających pewien stały graf jako podrzędny, pokrycie wierzchołka o rozmiarze k można znaleźć w czasie , tj. problem jest podwykładniczy o stałym parametrze, który można obliczyć . Algorytm ten jest ponownie optymalny w tym sensie, że zgodnie z hipotezą czasu wykładniczego żaden algorytm nie może rozwiązać pokrycia wierzchołków na grafach planarnych w czasie . ${\ Displaystyle 2 ^ {O ({\ sqrt {k}})} n ^ {O (1)}}$${\ Displaystyle 2 ^ {o ({\ sqrt {k}})} n ^ {O (1)}}$

Przybliżona ocena

Przybliżenie współczynnika 2 można znaleźć, wielokrotnie umieszczając oba punkty końcowe krawędzi w pokrywie wierzchołka, a następnie usuwając je z wykresu. Innymi słowy, znajdujemy maksymalne dopasowanie M za pomocą algorytmu zachłannego i konstruujemy pokrycie wierzchołków C, które składa się ze wszystkich punktów końcowych krawędzi w M . Na poniższym rysunku maksymalne dopasowanie M jest zaznaczone na czerwono, a pokrywa wierzchołka C jest oznaczona na niebiesko.

Tak skonstruowany zbiór C jest pokryciem wierzchołka: załóżmy, że krawędź e nie jest pokryta C ; wtedy M  ∪ { e } jest dopasowaniem, a e  ∉  M , co jest sprzeczne z założeniem, że M jest maksymalne. Co więcej, jeśli e  = { u ,  v } ∈ M , wtedy każde pokrycie wierzchołka – w tym optymalne pokrycie wierzchołka – musi zawierać u lub v (lub oba); w przeciwnym razie krawędź e nie jest zakryta. To znaczy, optymalne pokrycie zawiera co najmniej jeden punkt końcowy każdej krawędzi w M ; w sumie zbiór C jest co najwyżej 2 razy większy od optymalnego pokrycia wierzchołków.

Ten prosty algorytm został odkryty niezależnie przez Fanicę Gavril i Mihalisa Yannakakisa .

Bardziej zaangażowane techniki pokazują, że istnieją algorytmy aproksymacyjne o nieco lepszym współczynniku aproksymacji. Na przykład znany jest algorytm aproksymacji ze współczynnikiem aproksymacji równym . Problem można aproksymować współczynnikiem aproksymacji na gęstych grafach. ${\ Displaystyle 2-\ Theta \ lewo (1/{\ sqrt {\ log | V |}} \ po prawej)}$${\displaystyle 2/(1+\delta)}$${\ Displaystyle \ delta}$

Niezbliżalność

Nie jest znany lepszy algorytm aproksymacji współczynnika stałego niż powyższy. Problem minimalnego pokrycia wierzchołków to APX-complete , to znaczy, że nie można go arbitralnie dobrze aproksymować, chyba że P  =  NP . Wykorzystując techniki z twierdzenia PCP , Dinur i Safra udowodnili w 2005 r., że minimalne pokrycie wierzchołka nie może być aproksymowane ze współczynnikiem 1,3606 dla żadnego wystarczająco dużego stopnia wierzchołka, chyba że P  =  NP . Później współczynnik został poprawiony do dowolnego . Co więcej, jeśli hipoteza o unikalnych grach jest prawdziwa, to minimalne pokrycie wierzchołków nie może być aproksymowane w żadnym stałym współczynniku lepszym niż 2. ${\displaystyle {\sqrt {2}}-\epsilon}$${\ Displaystyle \ epsilon > 0}$

Chociaż znalezienie pokrycia wierzchołków o minimalnym rozmiarze jest równoważne znalezieniu zbioru niezależnego o maksymalnym rozmiarze, jak opisano powyżej, te dwa problemy nie są równoważne w sposób zachowujący przybliżenie: problem Niezależnego zbioru nie ma aproksymacji ze stałym współczynnikiem, chyba że P  =  NP .

Pseudo kod

APPROXIMATION-VERTEX-COVER(G)=
C = ∅
E'= G.E

while E' ≠ ∅:
    let (u, v) be an arbitrary edge of E'
    C = C ∪ {u, v}
    remove from E' every edge incident on either u or v

return C

Aplikacje

Optymalizacja pokrycia wierzchołków służy jako model dla wielu rzeczywistych i teoretycznych problemów. Na przykład przedsiębiorstwo komercyjne zainteresowane zainstalowaniem jak najmniejszej możliwej liczby kamer z obwodem zamkniętym obejmujących wszystkie korytarze (krawędzie) łączące wszystkie pomieszczenia (węzły) na podłodze może modelować cel jako problem minimalizacji pokrycia wierzchołków. Problem został również wykorzystany do modelowania eliminacji powtarzających się sekwencji DNA do zastosowań w biologii syntetycznej i inżynierii metabolicznej .

Uwagi

Bibliografia

Linki zewnętrzne

• Weisstein, Eric W. "Okładka wierzchołków" . MatematykaŚwiat .
• Weisstein, Eric W. „Minimalna osłona wierzchołków” . MatematykaŚwiat .
• Weisstein, Eric W. „Numer okładki wierzchołka” . MatematykaŚwiat .
• Przeprawy przez rzekę (i numery Alcuin) – Numberphile