Pokrivač čvorova

U oblasti matematike - teorija grafova, pokrivač čvorova za dati graf je takav skup čvorova da su sve grane tog grafa incidentne makar jednom čvoru tog skupa. Problem nalaženja minimalnog pokrivača čvorova je tipičan optimizacioni problem u računarstvu i standardan je primer NP-teškog optimizacionog problema koji se rešava aproksimacionim algoritmom. Odgovarajući problem odlučivanja, postojanje pokrivača čvorova, je jedan od Karpovih 21 NP-kompletnih problema i samim time jedan od osnovnih NP-kompletnih problema u teoriji kompleksnosti.

Problem minimalnog pokrivača čvorova se može definisati kao problem linearnog programiranja čiji je odgovarajući dualni linearni program određivanje maksimalnog uparivanja.

Definicija

Formalno, pokrivač čvorova neusmerenog grafa $G=(V,E)$ je podskup V′ od V takav da ako grana (u, v) pripada grafu G, onda u pripada V′ ili v pripada V′ ili oba čvora pripadaju V′. Skup V′ "pokriva" grane grafa G. Sledeće dve figure priakzuju primere pokrivača čvorova dva grafa (čvorovi skupa V' su označeni crvenom bojom).

Minimalni pokrivač čvorova je najmanji takav skup. Grčkim slovom $\tau$ označavamo veličinu minimalnog skupa pokrivača čvorova. Sledeće dve figure pokazuju minimalni skup pokrivača čvorova.

Primeri

• Skup svih čvorova je pokrivač čvorova.
• Čvorovi bilo kojeg skupa nezavisnih grana čine pokrivač čvorova.
• Za potpuni bipartitivni graf $K_{m,n}$ postoji minimalni pokrivač čvorova veličine $\tau (K_{m,n})=\min(m,n)$.

Osobine

• Skup čvorova V' je pokrivač čvorova ako njegov komplement u odnosu na skup svih čvorova čini skup nesusednih čvorova.
• Broj čvorova grafa je jednak ukupnom broju čvorova minimalnog pokrivača grana i maksimalnog skupa nesusednih čvorova.

Problem izračunljivosti

Problem nalaženja minimalnog pokrivača čvorova je optimizacioni problem pronalaženje najmanjeg pokrivača čvorova datog grafa.

ULAZ: Graf $G$

IZLAZ: Najmanje $k$ takvo da graf $G$ ima pokrivač čvorova veličine $k$.

Za problem definisan kao problem odlučivanja, naziva se problem pokrivača čvorova:

ULAZ: Graf $G$ prirodni broj $k$.

UPIT: Da li graf $G$ poseduje pokrivač čvorova veličine najviše $k$?

Problem odlučivosti pokrivača čvorova je NP-kompletan problem: je jedan od Karpovih 21 NP-kompletnih problema. Najčešće je korišćen pri teoriji kompleksnosti pri konstrukciji dokaza NP-teških problema.

CLP formulacija

Pridružimo svakom čvoru funkciju cene $c(v)\geq 0$. Problem težina minimalnog pokrivača čvorova se definiše sledećim celobrojnim linearnim programom (CLP).

minimize	$\sum _{v\in V}c(v)x_{v}$			(minimizuje ukupnu cenu)
subject to	$x_{u}+x_{v}\geq 1$	for all $\{u,v\}\in E$		(pokriva svaku granu grafa)
	$x_{v}\in \{0,1\}$	for all $v\in V$.		(svaki čvor ili pripada pokrivaču ili ne pripada)

Ovako definisan CLP pripada opštoj klasi CLP problema pokrivača.

Tačno izračunavanje

Problem odlučivosti pokrivača čvorova je NP-kompletan, što znači da je malo verovatno da postoji algoritam koji to efikasno rešava. NP-kompletnost se dokazuje redukcijom problema 3-zadovoljivosti ili redukcijom problema klike. Pokrivač čvorova ostaje NP-kompletan čak i u trostepenom grafu i u planarnom grafu stepena najviše 3.

Kod bipartitivnih grafova, jednakost problema pokrivača čvorova i problema maksimalnog uparivanja opisanog Konigovom teoremom omogućava rešavanje problema pokrivača grana bipartitivnog grafa u polinomijalnom vremenu.

Kod stabala, pohlepni algoritam nalazi minimalni pokrivač čvorova u polinomijalnom vremenu.

Izračunavanje aproksimacijom

Moguće je pronaći drugostepenu aproksimaciju konstantnim dodavanjem oba čvora izabrane grane u pokrivač čvorova, a zatim uklanjati ih sa grafa. Dakle, pronalazimo maksimalno uparivanje M pohlepnim algoritmom i konstruišemo pokrivač čvorova C koji sadrži ova kraja svih grana iz M. Na sledećoj figuri je maksimalno uprarivanje M označeno crvenom bojom, a pokrivač čvorova C plavom.

Skup C, konstruisan na ovaj način, je pokrivač čvorova: pretpostavimo da grana e nije pokrivena skupom C; tada je M ∪ {e} uparivanje i e ∉ M, što je kontradiktorno pretpostavci da je M maskimalno uparivanje. Dalje, ako e = {u, v} ∈ M, tada pokrivač čvorova, uključujući i optimalni pokrivač, mora sadržati u ili v (ili oba) jer u suprotnom grana e ne bi bila pokrivena. Dakle, Optimalni pokrivač čvorova sadrži makar jedan čvor svake grane iz M i ukupno, skup C je najviše dva puta veći od optimalnog pokrivača čvorova.

Ovaj algoritam su nezavisno osmislili Faniša Gavril i Mihalis Janakakis.

Naprednije tehnike pokazuju da postoji aproksimacioni algoritam sa nešto boljim stepenom optimizacije. Poznat je aproksimizacioni algoritam sa stepenom aproksimacije $2-\Theta \left(1/{\sqrt {\log |V|}}\right)$.

Neaproksimabilnost

Nije poznat algoritam sa boljim kostantnim stepenom aproksimacije od gorepomenutog. Problem minimalnog pokrivača čvorova je APIks-kompletan, što znači da se ne može proizvoljno dobro osim ako je P = NP. Koristeći tehnike PCB teoreme, 2005. godine su Dinur i Safra izneli dokaz da se minimalni pokrivač čvorova ne može aproksimizovati stepenom manjim od 1.3606 za dovoljno veliki stepen čvorova osim ako je P = NP.

Premda je pronalaženje minimalnog pokrivača čvorova ekvivalentno nalaženju maksimalnog nezavisnog skupa, kao što je gore opisano, ova dva problema nisu ekvivalentna u smislu očuvanja aproksimabilnosti: Problem nezavisnog skupa nema aproksimaciju konstantnog stepena osim ako važi P = NP.

Pseudo kôd

APROKSIMACIJA_POKRIVAČA_ČVOROVA(G)
C=∅
E'= G.E
dokle god je E'≠ ∅

neka je (u,v) proizvoljna grana iz E'

C = C ∪ {u,v}

izbaci iz E' svaku granu koja je incidentna ili sa u ili sa v

vrati C

Pokrivač čvorova kod hipergrafova

Za datu kolekciju skupova, skup koji u preseku sa svim skupovima te kolekcije sadrži makar jedan element se naziva udarnički skup i NP-težak problem je problem nalaženja udarničkog skupa najmanje veličine tj minimalnog udarničkog skupa. Preslikavanje skupova takve kolekcije na hipergraf se može shvatiti prirodnom generalizacijom problema pokrivača čvorova na hipergrafove i često se naziva pokrivač čvorova hipergrafa, a u kombinatornom smislu obilazak hipergrafa. Notacije udarničkog skupa i skupa pokrivača čvurova su identične.

Formalno, neka je H = (V, E) hipergraf sa skupom čvorova V i skupom hipergrana E. Tada se skup S ⊆ V naziva udarnički skup za H ako za sve grane e ∈ E važi S ∩ e ≠ ∅. Problemi teorije izračunljivosti minimalni udarnički skup i udarnički skup dafinisani su isto kao u slučaju grafova. Problem pokrivača čvorova običnog grafa je specijalan slučaj problema pokrivača čvorova hipergrafa čije su grane stepena 2.

Ako ograničimo problem veličinom d, problem nalaženja minimalnog d-udarničkog skupa se rešava d-aproksimacionim algoritmom. Ako pretpostavimo predlog jedinstvenih igara, onda je ovo najbolji aproksimacioni algoritam konstatnog stepena jer bi inače postojala mogućnost poboljšanja aproksimacije na d − 1.

Udarnički skup i pokrivač čvorova

Problem udarničkog skupa je ekvivalentat problemu pokrivača čvorova: Instanca problema pokrivača čvorova se može posmatrati kroz proizvoljni bipartitivni graf, sa skupovima predstavljenim čvorovima levo, elementima univerzuma predstavljenim čvorovima desno, pri čemu grane predstavljaju pripadnost elemenata tim skupovima. Zadatak je pronaći podskup levih čvorova minimalne kardinalnosti koji pokrivaju sve desne čvorove. U problemu udarničkog skupa, zadatak je pokriti sve leve čvorove koristeći minimalni podskup desnih čvorova. Svođenje jednog problema na drugi se postiže zamenom jednog skupa čvorova drugim.

Primene

Primer praktične primene koristeći problem udarničkog skupa se primećuje kod potrebe za efikasnom dinamičkom detekcijom uslova trke. U ovom primeru, svaki put kada se upisuje u globalnu memoriju, trenutna nit kao i skup katanaca koje drži ta nit će biti sačuvani. Kod detekcije zasnovane na skupu katanaca, ako druga nit pokuša da zapisuje podatke na toj lokaciji i nema trke, to znači da ona drži makar jedan zajednički katanac sa svim nitima koje su prethodno pisale na tom mestu. Dakle, veličina udarničkog skupa predstavlja minimalni skup katanaca potreban kako bi trka bila nemoguća. Ovo je korisno zarad eliminacije redudantnih pokušaja pisanja, jer se veliki skupovi katanaca smatraju nepoželjnim u praksi.

Literatura

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2013). Introduction to Algorithms. Delhi: PHI Learning Pvt. Ltd. str. 1109.