Set dominator conectat

Un set dominant conectat și un arbore care se întinde cu frunze maxime sunt două structuri strâns legate definite pe un grafic nedirecționat .

Definiții

O mulțime dominantă conexă a unui grafic G este o mulțime D de vârfuri cu două proprietăți:

  1. Din orice nod din D , puteți merge la orice alt nod din D de-a lungul unei căi care este complet în interiorul D. Adică, D generează un subgraf conex al graficului G.
  2. Orice vârf din G fie aparține lui D , fie este adiacent unui vârf din D. Adică, D este mulțimea dominantă a graficului G.

Mulțimea dominantă cel mai puțin conectată [1] a graficului G este mulțimea dominantă conexă cu cea mai mică cardinalitate dintre toate mulțimile dominante conectate ale graficului G . Numărul de dominanță conexă al unui grafic G este numărul de vârfuri din cea mai mică mulțime dominantă conexă [2] .

Orice arbore care se întinde T al unui grafic G are cel puțin două frunze. Un arbore care se întinde maxim de frunze este un arbore care are numărul maxim posibil de frunze dintre toți copacii întinderi din G . Numărul maxim de frunze din graficul G este numărul de frunze din arborele care se întinde cu frunziș maxim [3] .

Complementar

Dacă d este numărul de dominanță conex al unui grafic G cu n vârfuri, unde n > 2 și l este numărul maxim de frunze, atunci cele trei mărimi d , l și n sunt legate prin egalitate simplă

[4] .

Dacă D este o mulțime dominantă conectată, atunci există un arbore de întindere în G ale cărui frunze includ toate vârfurile care nu sunt în D - formăm un arbore de întindere al subgrafului generat de mulțimea D împreună cu muchiile care leagă fiecare vârf rămas v care nu se află în D cu vecinul său v un vârf aparținând lui D . Aceasta arată că l ≥ n − d .

În direcția opusă, dacă T este orice arbore care se întinde în G , atunci vârfurile non-frunze din arborele T formează o mulțime dominantă conexă a graficului G . Aceasta arată că n − l ≥ d . aceste două inegalităţi obţinute implică egalitatea n = d + l .

Astfel, în orice grafic, suma numărului de dominanță conectat și a numărului maxim de frunze este egală cu numărul de vârfuri ale graficului. Din punct de vedere computațional, aceasta înseamnă că calcularea numărului de dominanță conectat are aceeași dificultate ca și calcularea numărului maxim de frunze.

Algoritmi

Problema verificării dacă există o mulțime dominantă conectată cu o dimensiune mai mică decât un prag dat este NP-complet și o astfel de problemă este echivalentă cu verificarea dacă există un arbore care se întinde cu cel puțin un număr dat de frunze. Astfel, putem presupune că problema găsirii mulțimii dominante conexate minime și problema găsirii unui arbore întindere cu numărul maxim de frunze nu pot fi rezolvate în timp polinomial.

Când luăm în considerare problemele în termeni de algoritmi de aproximare, dominanța conectată și frunzișul copacului care se întinde maxim nu sunt aceleași - aproximarea unei probleme cu un coeficient de aproximare dat nu este același lucru cu aproximarea unei alte probleme cu același coeficient. Există o aproximare pentru problema găsirii celei mai mici mulțimi dominante conexate cu coeficientul 2 ln Δ + O(1) , unde Δ înseamnă gradul maxim de vârfuri din graficul G [5] . Sarcina de a găsi un arbore spanning cu frunziș maxim MAX-SNP este dificilă, ceea ce implică că, aparent, nu există o schemă de timp polinomială aproximativă [6] . Totuși, problema poate fi aproximată cu un factor de 2 în timp polinomial [7] .

Ambele probleme pot fi rezolvate pe grafice cu n vârfuri în timp O (1.9 n ) [8] . Problema frunzelor maxime este fix-parametric rezolvabilă , ceea ce înseamnă că poate fi rezolvată în timp care depinde exponențial de numărul de frunze, dar numai polinom de dimensiunea graficului. Valoarea a acestor algoritmi (în mod intuitiv, acesta este numărul de frunze pentru care algoritmul rulează într-un timp acceptabil) a crescut treptat pe măsură ce algoritmii s-au îmbunătățit la aproximativ 37 [9] și există sugestii că o valoare de 50 poate fi atins [10] .

Aplicații

Seturile dominante conectate sunt utile pentru calcularea rutelor pentru rețelele wireless descentralizate auto-organizate . În aceste aplicații, un mic set dominant conectat este folosit ca coloană vertebrală de transmisie a datelor, iar nodurile care nu aparțin acestui set transmit mesaje prin vecinii aflați pe coloana vertebrală [11] .

Numărul maxim de frunze este utilizat pentru a dezvolta algoritmi fixați-parametric rezolvabili - unele probleme de optimizare NP-hard pot fi rezolvate în timp polinomial pe grafice cu un număr maxim limitat de frunze [3] .

Vezi și

Note

  1. ↑ Setul Dominator Minimal Conectat apare adesea . În literatura în limba rusă, există o mare confuzie a cuvintelor maxim și mai mare (respectiv, minim și minim ). De obicei, maximul este înțeles ca un element care nu poate fi extins, iar maximul este înțeles ca un element cu caracteristica numerică maximă (comparați, de exemplu, potrivirea maximă și potrivirea cea mai mare )
  2. ↑ Sampathkumar, Walikar, 1979 , p. 607–613.
  3. ↑ 1 2 Fellows, Lokshtanov, Misra et al., 2009 , p. 822–848.
  4. ↑ Douglas, 1992 , p. 41–47.
  5. ↑ Guha, Khuller, 1998 , p. 374–387.
  6. ↑ Galbiati, Maffioli, Morzenti 1994 , p. 45–49.
  7. ↑ Solis-Oba, 1998 , p. 441–452.
  8. ↑ Fernau, Kneis, Kratsch et al., 2011 , p. 6290–6302.
  9. ↑ Binkele-Raible, Fernau, 2014 , p. 179–200.
  10. ↑ Fellows, McCartin, Rosamond, Stege, 2000 , p. 240–251.
  11. ↑ Wu, Li, 1999 , p. 7–14.

Literatură