Problemă de acoperire a vertexului

Coperta vertexului, cunoscută și în engleză vertex cover, aparține clasei de echivalență a problemelor complete nedeterministe, împreună cu problema vânzătorului călător , problema rucsacului etc.

Această clasă de probleme se numește NP-completă , adică se spune că problema acoperirii vertexului este o problemă NP-completă. În această privință, dovada echivalenței între toate problemele NP-complete este utilă, așa cum sa afirmat. Folosind aceste probleme, de exemplu, se obțin modele pentru logistică sau pentru calcularea costurilor în producție. Problema complementară este acoperirea vârfului respectiv acoperirea marginii sau acoperirea marginii .

În informatică , problema acoperirii vertexului este o problemă NP-completă și a fost una dintre cele 21 probleme ale NP-complete ale lui Richard Karp . Este adesea folosit în complexitatea de calcul pentru a demonstra completitudinea NP a problemelor mai complicate.

Definiție

O acoperire de vârf a unui grafic nedirecționat $G=(V,E)$ ${\ displaystyle G = (V, E)}$ ${\ displaystyle G = (V, E)}$ este un subset $S.$ ${\ displaystyle S}$ $S.$ dintre vârfurile sale astfel încât fiecare arc să aibă cel puțin un capăt în $S.$ ${\ displaystyle S}$ $S.$ .

Problema de acoperire a vertexului este problema de optimizare combinatorie a găsirii celei mai mici acoperiri a vertexului într-un grafic.

Acoperirea managementului superior este strâns legată de cel mai înalt set independent . Un set de vârfuri este un capac de vârf dacă și numai dacă complementul său ${\bar {S}}=V\setminus S$ ${\ displaystyle {\ bar {S}} = V \ setminus S}$ ${\ displaystyle {\ bar {S}} = V \ setminus S}$ este un set independent. Rezultă că un grafic cu $n$ ${\ displaystyle n}$ $n$ vârfurile sunt acoperite de vârfurile cardinalității $k$ ${\ displaystyle k}$ $k$ dacă și numai dacă graficul are un set independent de cardinalitate $n-k$ ${\ displaystyle nk}$ $n-k$ . În acest sens, cele două probleme sunt duale.

Tractabilitate

Problema deciziei asociată cu problema acoperirii vertexului este NP-completă , ceea ce înseamnă că nu există cu greu un algoritm eficient care să o rezolve exact. Completitatea NP poate fi demonstrată prin reducerea de la 3SAT sau, așa cum a făcut Karp , prin reducerea de la problema fisurilor . Acoperirea vertexului rămâne NP-completă și în graficele cubice ^[1] și în graficele plane de grad cel puțin 3 ^[2] .

Într-un grafic bipartit , echivalența dintre acoperirea vertexului și cuplarea maximă descrisă de teorema lui König permite rezolvarea problemei acoperirii vertexului în graficele bipartite în timp polinomial .

S-a rezolvat tratabilitatea parametrilor

Deși problema acoperirii vertexului este NP-completă , un algoritm de forță brută poate rezolva problema în timp $2^{{\mathcal {O}}(k)}n^{{\mathcal {O}}(1)}$ ${\ displaystyle 2 ^ {{\ mathcal {O}} (k)} n ^ {{\ mathcal {O}} (1)}}$ ${\ displaystyle 2 ^ {{\ mathcal {O}} (k)} n ^ {{\ mathcal {O}} (1)}}$ . Acoperirea vârfurilor este, prin urmare, negociabilă cu un parametru fix și dacă suntem interesați doar de valori mici ale $k$ ${\ displaystyle k}$ $k$ , putem rezolva problema în timp polinomial. Strategia algoritmului forței brute este de a alege un vârf și de a face salturi recursive, cu două cazuri la fiecare pas: introduceți vârful curent sau toate vârfurile adiacente acestuia în acoperirea vârfului. Sub ipoteze rezonabile ale teoriei complexității de calcul, acest timp de rulare nu poate fi îmbunătățit $2^{o(k)}n^{{\mathcal {O}}(1)}$ ${\ displaystyle 2 ^ {o (k)} n ^ {{\ mathcal {O}} (1)}}$ ${\ displaystyle 2 ^ {o (k)} n ^ {{\ mathcal {O}} (1)}}$ .

Cu toate acestea, într-un grafic plan , o acoperire prin vârfuri de cardinalitate $k$ ${\ displaystyle k}$ $k$ pot fi găsite în timp $2^{{\mathcal {O}}({\sqrt {k}})}n^{2}$ ${\ displaystyle 2 ^ {{\ mathcal {O}} ({\ sqrt {k}})} n ^ {2}}$ ${\ displaystyle 2 ^ {{\ mathcal {O}} ({\ sqrt {k}})} n ^ {2}}$ , adică problema este sub-exponențială în raport cu tractabilitatea parametrilor fixi. Acest algoritm este din nou excelent, în sensul că, sub aceleași ipoteze ale teoriei complexității de calcul, niciun algoritm nu poate rezolva problema acoperirii cu vârfuri în grafice plane în timp $2^{o({\sqrt {k}})}n^{{\mathcal {O}}(1)}$ ${\ displaystyle 2 ^ {o ({\ sqrt {k}})} n ^ {{\ mathcal {O}} (1)}}$ ${\ displaystyle 2 ^ {o ({\ sqrt {k}})} n ^ {{\ mathcal {O}} (1)}}$ . ^[3]

Aproximabilitate

Este posibil să se găsească un algoritm de aproximare cu 2 factori luând în mod repetat ambele capete ale unui arc în acoperirea vertexului, apoi îndepărtându-le din grafic. Nu se cunoaște nicio aproximare cu factori constanți mai buni; problema este APX-completă , adică nu poate fi aproximată cu precizie arbitrară. În special, acoperirea minimă prin vârfuri poate fi aproximată în $2-\Theta \left({\frac {1}{\sqrt {\log |V|}}}\right)$ ${\ displaystyle 2- \ Theta \ left ({\ frac {1} {\ sqrt {\ log | V |}}} \ right)}$ ${\ displaystyle 2- \ Theta \ left ({\ frac {1} {\ sqrt {\ log | V |}}} \ right)}$ pentru un dat $V\geq 2$ ${\ displaystyle V \ geq 2}$ ${\ displaystyle V \ geq 2}$ ^[4] dar nu poate fi aproximat cu un factor de 1,3606 pentru niciun grad de vârfuri suficient de mare decât dacă P = NP. ^[5]

Deși găsirea acoperirii prin vârfuri de cardinalitate minimă este echivalentă cu găsirea unui set independent de cardinalitate maximă, cele două probleme nu sunt echivalente în ceea ce privește aproximabilitatea. Problema setului independent nu are aproximări ale factorilor constanți decât dacă P = NP .