Set dominant

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 24 februarie 2021; verificarea necesită 1 editare .

În teoria grafurilor, mulțimea dominantă pentru un graf G = ( V , E ) este o submulțime D a mulțimii de vârfuri V , astfel încât orice vârf care nu este în D este adiacent cu cel puțin un element din D . Numărul de dominanță γ( G ) este numărul de vârfuri din cea mai mică mulțime dominantă G .

Problema mulțimii dominante este de a verifica dacă inegalitatea γ( G ) ≤ K este adevărată pentru un grafic G dat și un număr K . Problema este o problemă clasică de solubilitate NP-completă în teoria complexității computaționale [1] . Astfel, se crede că nu există un algoritm eficient pentru a găsi cea mai mică mulțime dominantă pentru un grafic dat.

Figurile (a)-(c) din dreapta arată trei exemple de seturi de grafice dominante. În aceste exemple, fiecare vârf alb este adiacent cel puțin unui vârf roșu, iar vârfurile albe se spune că sunt dominate de vârfurile roșii. Numărul dominant al acestui grafic este 2 - exemplele (b) și (c) arată că există o mulțime dominantă cu 2 vârfuri și se poate verifica că pentru acest grafic nu există o mulțime dominantă cu un singur vârf.

Istorie

După cum au remarcat Hedeenimi și Laskar [2] , problema dominanței a fost studiată încă din anii 1950, dar numărul de studii asupra dominanței a crescut substanțial la mijlocul anilor 1970. Bibliografia lor include peste 300 de lucrări legate de dominanța graficului.

Borduri

Fie G  un grafic cu n ≥ 1 vârfuri și fie Δ gradul maxim al graficului. Următoarele limite γ( G ) [3] sunt cunoscute :

dominație independentă

Mulțimile dominante sunt strâns legate de mulțimile  independente — o mulțime independentă este dominantă dacă și numai dacă este cea mai mare mulțime independentă , deci orice cea mai mare mulțime independentă [4] dintr-un grafic este și cea mai mică mulțime dominantă. Numărul de dominanță independent i ( G ) al lui G  este dimensiunea celei mai mici mulțimi independente dominante (sau, echivalent, dimensiunea minimă a celor mai mari mulțimi independente).

Mulțimea dominantă minimă dintr-un grafic nu este neapărat independentă, dar dimensiunea mulțimii dominante minime este întotdeauna mai mică sau egală cu dimensiunea celei mai mari mulțimi independente minime, adică γ( G ) ≤ i ( G ).

Există familii de grafice în care cea mai mare mulțime independentă minimă este mulțimea minimă dominantă. De exemplu, Allan și Lascar [5] au arătat că γ( G ) = i ( G ) dacă G nu are gheare .

Un grafic G este numit un grafic dominant perfect dacă γ( H ) = i ( H ) în orice subgraf generat H din G. Deoarece subgraful generat al unui graf fără gheare este fără gheare, rezultă că orice graf fără gheare este perfect perfect [6] .

Exemple

Figurile (a) și (b) arată mulțimi dominante independente, în timp ce figura (c) arată o mulțime care nu este independentă.

Pentru orice grafic G , graficul său de linii L ( G ) este fără gheare și, prin urmare, cea mai mare mulțime independentă minimă din L ( G ) este, de asemenea, mulțimea dominantă minimă din L ( G ). O mulțime independentă în L ( G ) corespunde unei potriviri în G , iar o mulțime dominantă în L ( G ) corespunde unei mulțimi dominante de muchie în G . Astfel, cea mai mare potrivire minimă are aceeași dimensiune ca setul dominant de margine minimă.

Algoritmi și complexitate computațională

Există o pereche de L-reduceri în timp polinomial între problema mulțimii dominante minime și problema de acoperire a mulțimii [7] . Aceste reduceri (vezi mai jos) arată că un algoritm eficient pentru problema setului dominant minim ar da un algoritm eficient pentru problema setului de acoperire și invers. Mai mult, reducerile păstrează factorul de aproximare  — pentru orice α, un algoritm de α-aproximare în timp polinomial pentru găsirea unei mulțimi dominante minime ar oferi un algoritm de α-aproximare în timp polinomial pentru problema de acoperire a mulțimii și invers. Ambele sarcini sunt, de fapt, Log-APX-complete [8] .

Problema de acoperire a mulțimii este o problemă binecunoscută NP-hard - problema de acoperire a mulțimii într-o variantă a problemei de solubilitate a fost una dintre cele 21 de probleme NP-complete ale lui Karp , pentru care NP-completitudinea a fost dovedită încă din 1972. Reductibilitatea arată că problema setului dominant este, de asemenea, NP-hard.

Aproximabilitatea problemei de acoperire a seturilor este, de asemenea, bine înțeleasă - factorul de aproximare logaritmică poate fi găsit folosind un algoritm simplu lacom , iar găsirea factorului sublogaritmic și logaritmic este o problemă NP-hard. Mai precis, algoritmul greedy produce un factor de aproximare de 1 + log | v | pentru mulțimea dominantă minimă, iar Raz și Safra [9] au arătat că niciun algoritm nu dă un factor de aproximare mai bun decât C *log | v | pentru unele C > 0 cu excepția cazului în care P = NP .

L-casts

Următoarea pereche de reduceri [7] arată că problema mulțimii dominante minime și problema de acoperire a mulțimii sunt echivalente în L-reducere  — având în vedere o problemă, putem construi o declarație echivalentă a celeilalte probleme.

De la setul dominant la setul de acoperire. Având în vedere un grafic G = ( V , E ) cu V = {1, 2, …, n }, construim o acoperire a mulțimii ( U , S ) după cum urmează: Mulțimea U este egală cu V și familia de submulțimi este egală cu S = { S 1 , S 2 , …, S n }, unde S v constă din vârful v și toate vârfurile adiacente v vârfuri din G .

Acum, dacă D este o mulțime dominantă în G , atunci C = { S v  : v ∈ D } este o soluție fezabilă pentru problema de acoperire cu | c | = | D |. În schimb, dacă C = { S v  : v ∈ D } este o soluție fezabilă pentru problema de acoperire, atunci D este o mulțime dominantă pentru G cu | D | = | C |.

Prin urmare, dimensiunea setului dominant minim pentru G este egală cu dimensiunea acoperirii setului minim pentru ( U , S ). Mai mult, există un algoritm simplu care mapează un set dominant la un set de acoperire de aceeași dimensiune și invers. În special, un algoritm eficient de α-aproximare pentru acoperirea seturilor produce un algoritm eficient de α-aproximare pentru seturile dominante minime.

De exemplu, având în vedere graficul G prezentat în dreapta, construim o acoperire cu mulțimea U = {1, 2, …, 6} și submulțimile S 1 = {1, 2, 5}, S 2 = {1, 2, 3, 5}, S 3 = {2, 3, 4, 6}, S 4 = {3, 4}, S 5 = {1, 2, 5, 6} și S 6 = {3, 5, 6}. În acest exemplu, D = {3, 5} este mulțimea dominantă pentru G  - corespunde acoperirii C = { S 3 , S 5 }. De exemplu, vârful 4 ∈ V este dominat de vârful 3 ∈ D , iar elementul 4 ∈ U este conținut în mulțimea S 3 ∈ C .

De la acoperirea unui set la un set dominant. Fie ( S , U ) o soluție la problema de acoperire a mulțimii cu colecția U și familia de submulțimi S = { S i  : i ∈ I }. Presupunem că U și mulțimea de indici I nu se intersectează. Construim graficul G = ( V , E ) după cum urmează. Luați V = I ∪ U ca mulțime de vârfuri . Definim o muchie { i , j } ∈ E între fiecare pereche i , j ∈ I , precum și o muchie { i , u } pentru fiecare i ∈ I și u ∈ S i . Adică, G este un grafic divizat  - I este o clică și U este o mulțime independentă .

Acum, dacă C = { S i  : i ∈ D } este o soluție fezabilă a problemei de acoperire a mulțimii pentru o submulțime D ⊆ I , atunci D este o mulțime dominantă pentru G cu | D | = | C |: În primul rând, pentru orice vârf u ∈ U , există i ∈ D astfel încât u ∈ S i , și, prin construcție, u și i sunt adiacente în G . Prin urmare - u este dominat de vârful i . În al doilea rând, deoarece D trebuie să fie nevid, orice i ∈ I este adiacent unui vârf din D .

În schimb, să fie D o mulțime dominantă pentru G . Apoi putem construi o altă mulțime dominantă X astfel încât | x | ≤ | D | iar X ⊆ I  înlocuiește pur și simplu fiecare vârf u ∈ D ∩ U cu un vârf i ∈ I adiacent lui u . Atunci C = { S i  : i ∈ X } este o soluție fezabilă a problemei de acoperire cu | c | = | x | ≤ | D |.

Figura din dreapta arată construcția pentru U = { a , b , c , d , e }, I = {1, 2, 3, 4}, S 1 = { a , b , c }, S 2 = { a , b } , S 3 = { b , c , d } și S 4 = { c , d , e }. În acest exemplu, C = { S 1 , S 4 } este acoperirea setului. Ea corespunde multimii dominante D = {1, 4}. D = { a , 3, 4} este o altă mulțime dominantă pentru graficul G . Având în vedere D , putem construi o mulțime dominantă X = {1, 3, 4} care nu depășește D și este o submulțime a lui I . Mulțimea dominantă X corespunde acoperirii mulțimii C = { S 1 , S 3 , S 4 }.

Ocazii speciale

Dacă graficul are un grad maxim Δ, atunci algoritmul de aproximare greedy găsește o aproximare O (log Δ) a mulțimii dominante minime. De asemenea, să fie d g puterea mulțimii dominante obținută folosind algoritmul de aproximare greedy, atunci următoarea relație este valabilă: d g ≤ N+1 - , unde N este numărul de noduri și M este numărul de muchii dintr-un anumit grafic nedirecționat [10] . Pentru un Δ fix, aceasta înseamnă că problema găsirii mulțimii dominante aparține clasei APX . De fapt, problema este APX-complet [11] .

Algoritmul permite PTAS pentru cazuri speciale, cum ar fi graficele cercului unitar și graficele plane [12] . Mulțimea dominantă minimă poate fi găsită în timp liniar în grafice paralel-secvențiale [13] .

Algoritmi exacti

Mulțimea minimă dominantă a unui grafic cu n vârfuri poate fi găsită în timp O (2 n n ) analizând toate submulțimile de vârfuri. Fomin, Grandoni și Kratch au arătat [14] cum să găsească setul dominant minim în O (1,5137 n ) timp folosind memoria exponențială și O (1,5264 n ) timp folosind memoria polinomială. Un algoritm mai rapid care rulează în timp O (1,5048 n ) a fost găsit de von Roy, Nederlof și von Dijk [15] , care au arătat că numărul de seturi dominante minime poate fi calculat în timpul specificat. Numărul de mulțimi dominante minime nu depășește 1,7159 n și toate astfel de mulțimi pot fi enumerate în timp O (1,7159 n ) [16] .

Complexitatea parametrică

Căutarea unui set dominant de mărime k joacă un rol central în teoria complexității parametrice. Problema este cea mai cunoscută problemă W[2]-completă și este folosită în multe cazuri pentru a arăta insolubilitatea problemei prin reducerea acesteia la problema găsirii mulțimii dominante. În special, problema nu este solubilă cu parametri fixe (FPR) în sensul că nu există un algoritm cu timp de rulare f ( k ) n O(1) pentru orice funcție f , cu excepția cazului în care ierarhia W se prăbușește în FPT =W[2].

Pe de altă parte, dacă graficul de intrare este plan, problema rămâne NP-hard, dar algoritmul cu un parametru fix este cunoscut. De fapt, problema are un nucleu cu o dimensiune liniară în k [17] , iar un timp de rulare care este exponențial în √ k și cubic în n poate fi atins prin aplicarea programării dinamice la ramificarea nucleului [18] . Mai general, problema mulțimii dominante și multe variante ale problemei sunt rezolvabile fix-parametric dacă parametrizarea este efectuată atât în ​​ceea ce privește dimensiunea mulțimii dominante, cât și în ceea ce privește dimensiunea celui mai mic subgraf bipartit complet interzis . Adică problema este un FPR pe grafuri fără biclicuri , o clasă destul de generală de grafuri rare, care include grafuri plane [19] .

Opțiuni

Conjectura lui Vizing leagă numărul de dominanță al unui produs direct al graficelor de numerele de dominanță ale factorilor săi.

Există multe lucrări despre setul dominant conectat . Dacă S este o mulțime dominantă conexă, se poate forma un arbore de acoperire a lui G în care S formează mulțimea vârfurilor non-frunze ale arborelui . În schimb, dacă T este un arbore de acoperire al unui grafic cu mai mult de două vârfuri, vârfurile non-frunze ale lui T formează o mulțime dominantă conexă. Astfel, căutarea unor seturi dominante conectate minime este echivalentă cu căutarea copacilor care se întind cu numărul maxim posibil de frunze.

O mulțime dominantă completă  este un set de vârfuri astfel încât toate vârfurile graficului (inclusiv vârfurile mulțimii dominante în sine) au vecini în mulțimea dominantă. Figura (c) de mai sus arată un set dominant care este atât un set dominant conectat, cât și un set dominant complet în același timp. În figurile (a) și (b), mulțimile dominante nu sunt niciuna.

O mulțime dominantă de k-tuplu  este o mulțime de vârfuri astfel încât fiecare vârf din grafic are cel puțin k vecini în mulțime. Aproximația (1+log n) a unei mulțimi dominante de k-tuplu minim poate fi găsită în timpul polinomial [20] . În mod similar, o mulțime k-dominantă  este o mulțime de vârfuri astfel încât fiecare vârf care nu este în mulțime are cel puțin k vecini în mulțime. În timp ce orice grafic admite o mulțime k-dominantă, numai graficele cu un grad minim de k-1 permit o mulțime dominantă de k-tuplu. Totuși, chiar dacă graficul permite o mulțime dominantă de k-tuplu, setul minim de dominare de k-tuplu poate fi de aproape k ori mulțimea minimă de dominare de k-tuplu pentru același grafic [21] . Aproximația (1,7+log Δ) a mulțimii k-dominante minime poate fi găsită și în timp polinomial.

O descompunere domatică  este o descompunere a vârfurilor în mulțimi dominante care nu se suprapun. Un număr domatic este dimensiunea maximă a unei expansiuni domatice.

Mulțimea eternă dominantă  este o versiune dinamică a dominanței în care un vârf v din mulțimea dominantă D este ales și înlocuit cu un u vecin ( u nu în D ) în așa fel încât și mulțimea modificată D este dominantă și acest proces poate se repetă pentru orice succesiune finită de opțiuni de vârf v.

Software pentru găsirea setului dominant minim

Nume Licență Limba utilizatorului informatii scurte
openopt BSD Piton Utilizează grafice NetworkX . Poate folosi pachete gratuite și comerciale. Consultați pagina setului dominant pentru detalii și exemple .

Vezi și

Note

  1. ↑ Gary, Johnson, 1982 , p. 235, Sarcina TG2.
  2. ↑ Hedetniemi, Laskar, 1990 .
  3. ↑ Haynes, Hedetniemi, Slater, 1998a , p. capitolul 2.
  4. ↑ Există adesea o confuzie cu termenii cea mai mare set și maxim . În acest articol, cel mai mare set este înțeles ca un set care nu poate fi extins păstrându-și proprietatea. Un set maxim este un set cu o proprietate dată care are o dimensiune maximă.
  5. ↑ Allan, Laskar, 1978 .
  6. ↑ Faudree, Flandrin, Ryjaček, 1997 .
  7. ↑ 1 2 Kann, 1992 , p. 108–109.
  8. ↑ Escoffier, Paschos, 2006 , p. 369–377.
  9. ↑ Raz, Safra, 1997 .
  10. ↑ Parekh, 1991 , p. 237-240.
  11. ↑ Papadimitriou, Yannakakis, 1991 , p. 425–440.
  12. ↑ Crescenzi, Kann, Halldorsson, Karpinski, 2000 .
  13. ↑ Takamizawa, Nisizeki, Saito, 1982 .
  14. ↑ Fomin, Grandoni, Kratsch, 2009 .
  15. ↑ van Rooij, Nederlof, van Dijk, 2009 .
  16. ↑ Fomin, Grandoni, Pyatkin, Stepanov, 2008 .
  17. ↑ Alber, Fellows, Niedermeier, 2004 .
  18. ↑ Fomin, Thilikos, 2006 .
  19. ↑ Telle, Villagenger, 2012 .
  20. ↑ Klasing, Laforest, 2004 .
  21. ↑ Forster, 2013 .

Literatură