Problema setului independent

Problema multimii independente apartine clasei de probleme NP-complete din domeniul teoriei grafurilor . Echivalent cu problema clicei .

Definiții

Un set de vârfuri dintr-un grafic se numește independent dacă nu există două vârfuri din această mulțime conectate printr-o muchie. Cu alte cuvinte, subgraful indus de această mulțime este format din vârfuri izolate. Se mai spune uneori că fiecare muchie a unui graf este incidentă cu cel mult un vârf dintr-o mulțime independentă. Problema recunoașterii (problema decidabilitatii) arată astfel: un grafic dat G are o mulțime independentă de mărime k ? Problema de optimizare corespunzătoare acesteia, cunoscută și sub denumirea de problemă a mulțimii independente , este formulată astfel: într-un grafic dat G , se cere să se găsească o mulțime independentă de dimensiune maximă. Această mărime se numește numărul de independență , numărul de densitate internă sau looseness și se notează ca [1] [2] .

Această problemă este uneori denumită găsirea celui mai mare set independent . Acest concept nu trebuie confundat cu mulțimea independentă maximă sau cu mulțimea independentă maximă prin includere , care este definită ca un astfel de set independent de vârfuri încât atunci când se adaugă încă un (orice) vârf al graficului original, acesta încetează să mai fie. fi independent (în general vorbind, pot exista astfel de seturi de mai multe și de dimensiuni diferite). O mulțime independentă de incluziune maximă nu este întotdeauna cea mai mare. În același timp, fiecare cea mai mare mulțime independentă este, prin definiție, și maximă prin includere. Pentru a găsi (unele) mulțimi independente maxime în ceea ce privește includerea, se poate folosi un algoritm lacom care rulează în timp polinomial, în timp ce problema celei mai mari mulțimi independente aparține clasei de probleme NP-complete.

Un set independent de incluziune maximă este un set dominant . Orice grafic conține maximum 3 n /3 mulțimi independente de incluziune maximă [3] , dar majoritatea graficelor au mult mai puține dintre ele.

Numărul de mulțimi independente de incluziune maximă în cicluri de n vârfuri este numere Perrin , iar numărul de mulțimi independente de incluziune maximă în căi cu n vârfuri este dat de șirul Padovan [4] . Astfel, ambele numere sunt proporționale cu puterea lui 1,324718, numărul plastic .

Cea mai mică submulțime independentă dintr-un grafic este orice vârf al acelui grafic.

Relația cu alți parametri ai graficului

O mulțime este independentă dacă și numai dacă este o clică în complementul grafului , astfel încât cele două concepte să se completeze reciproc. Graficele suficient de mari fără clicuri mari au mulțimi independente mari, ceea ce este subiectul de studiu în teoria Ramsey .

O mulțime este independentă dacă și numai dacă complementul său este o acoperire de vârf . Suma numărului de independență și a numărului de acoperire a vârfurilor este egală cu numărul de vârfuri din grafic (prima identitate Gallai ).

Colorarea vârfurilor unui grafic corespunde împărțirii vârfurilor acestuia în submulțimi independente. Prin urmare, numărul minim de culori necesare pentru a colora vârfurile, numărul cromatic , nu este mai mic decât câtul dintre numărul de vârfuri și numărul de independență .

În graficele bipartite care nu au vârfuri izolate, numărul de vârfuri din cea mai mare mulțime independentă este egal cu numărul de muchii din cea mai mică acoperire a muchiei (o consecință a teoremei lui König ).

Căutați seturi independente

În informatică sunt studiate mai multe probleme de calcul legate de mulțimi independente:

Primele trei probleme sunt importante în aplicațiile practice, în timp ce ultima este importantă pentru teoria NP-completitudinii pentru probleme legate de mulțimi independente.

Problema mulțimii independente și problema clicei sunt duale: o clică în G  este o mulțime independentă în complementul lui G și invers. Astfel, multe rezultate computaționale pot fi aplicate la fel de bine la ambele probleme. De exemplu, rezultatele asociate cu problema clicei au următoarele consecințe:

Găsirea celui mai mare set independent

Această problemă este uneori denumită „ ambalaj de vârf ”.

Cea mai mare problemă de mulțime independentă și cea mai mare problemă de clică sunt echivalente polinomial - se poate găsi cea mai mare mulțime independentă găsind clica maximă în complementul graficului, așa că mulți autori nu le pasă în mod special de separarea celor două probleme. Ambele probleme sunt NP-complete, deci este puțin probabil ca acestea să fie rezolvate în timp polinomial. Cu toate acestea, cea mai mare problemă de mulțime independentă poate fi rezolvată mai eficient decât în ​​timpul O( n 2  2 n ), ceea ce conduce la o căutare exhaustivă care testează toate submulțimile de vârfuri pentru a vedea dacă sunt mulțimi independente. Algoritmul lui Robson [6] rezolvă problema în timp O(2 0,276 n ) folosind spațiul exponențial. Dacă există o limită a mărimii (spațiul polinomial), există un algoritm pentru rezolvarea în timp O*(1.2127 n ) [7] .

În ciuda relației strânse dintre cea mai mare clică și cea mai mare mulțime independentă dintr-un grafic arbitrar, problemele de a găsi o mulțime independentă și o clică pot diferi semnificativ atunci când sunt rezolvate pe o clasă specială de grafice. De exemplu, pentru graficele rare (grafice în care numărul de muchii din orice subgraf nu este mai mare decât numărul de vârfuri înmulțit cu o constantă), clica cea mai mare are o dimensiune limitată și poate fi găsită exact în timp liniar [8] . Cu toate acestea, pentru aceleași clase de grafice, sau chiar pentru cazul unor restricții mai stricte pentru o clasă de grafice cu grad mărginit, căutarea celei mai mari mulțimi independente este MAXSNP-complet , ceea ce înseamnă că pentru o constantă c (în funcție de pe grad) NP - este greu de găsit o soluție aproximativă care să difere cu un factor c de cea optimă [9] . Cu toate acestea, sunt cunoscuți algoritmi eficienți aproximativi, dar eficiența lor garantată este mai slabă decât acest prag. De exemplu, un algoritm lacom creează un set independent de incluziune maximă prin alegerea unui vârf cu gradul minim la fiecare pas și eliminând vecinii săi. Acest algoritm realizează eficiență garantată (Δ+2)/3 pe grafice cu grad maxim Δ [10] .

În unele clase de grafuri (inclusiv grafuri fără gheare [11] și grafuri perfecte [12] ; arborii aparțin de asemenea acestei din urmă clasă ), cea mai mare mulțime independentă poate fi găsită în timp polinomial. Pentru graficele plane , cea mai mare problemă de mulțime independentă rămâne NP-completă pentru o soluție exactă, dar poate fi aproximată cu orice eficiență garantată c  < 1 în timp polinomial. Scheme de timp polinomiale aproximative similare există în orice familie de grafice minor închise [13] [14] .

În graficele bipartite, toate vârfurile care nu se află în cea mai mică acoperire a nodurilor pot fi incluse în cea mai mare mulțime independentă (vezi teorema lui König ). Prin urmare, cea mai mare mulțime independentă poate fi găsită folosind algoritmul pentru găsirea celor mai mari potriviri în graficele bipartite.

Căutați seturi independente de incluziune maximă

Toate seturile independente de incluziune maximă pot fi găsite în timp O(3 n /3 ).

Software pentru găsirea de seturi independente

Nume Licență Limbajul API Descriere
igraf GPL C, Python, R, Ruby solutie exacta
NetworkX BSD Piton soluție aproximativă, vezi procedura maximum_independent_set
openopt BSD Piton soluții exacte și aproximative, capacitatea de a specifica vârfurile care ar trebui incluse/excluse. Consultați clasa STAB pentru detalii și exemple

Cel mai mare set independent dintr-un copac

Daca graficul dat este un arbore , atunci problema multimii independente este rezolvata eficient prin programare dinamica .

Substructura optimă a problemei

Structura arborelui în sine sugerează soluția problemei. Și anume, notăm orice vârf ca rădăcină a arborelui și îl numim . Să notăm dimensiunea celui mai mare set independent de vârfuri a subarborelului a cărui rădăcină este vârful . Atunci răspunsul la problemă va fi .

Este ușor de observat că dacă includem vârful u în cea mai mare mulțime independentă, atunci cardinalitatea lui crește cu 1, dar nu îi putem lua copiii (deoarece sunt legați printr-o muchie de vârful u ); dacă nu includem acest vârf, atunci cardinalitatea celei mai mari mulțimi independente va fi egală cu suma dimensiunilor mulțimilor independente de copii ai acestui vârf. Rămâne doar să alegeți maximul dintre aceste două opțiuni pentru a obține o soluție la problemă:

unde nepot denotă orice „nepot” al vârfului, iar copil denotă orice descendent al vârfului.

Pseudocod

Considerăm că în partea de sus u este stocat :

funcția get_independent_set(Nodul u) { dacă I(u) a fost deja calculat, atunci returnează I(u) // cardinalitatea mulțimii care se poate obține dacă nu luăm vârful u sumă_copii = 0 // cardinalitatea mulțimii care se poate obține luând vârful u suma_nepoților = 0 // buclă prin toți copiii for i := 1 to child_num do sumă_copii = suma_copii + get_independent_set(copii[i]) // buclă prin toți nepoții pentru i:= 1 la num_nepoți suma_nepoților = suma_nepoților + get_independent_set(nepoții[i]) // amintiți-vă, ca să nu recalculăm din nou I(u) = max(1 + suma_nepoților, suma_copiilor) returnează eu (u) }

Apelarea get_independent_set( r ) va oferi răspunsul la problemă. Timpul de execuție al algoritmului este evident O (|V| + |E|).

Vezi și

Note

  1. ↑ Chris Godsil, Gordon Royle. . Teoria algebrică a graficelor. - New York: Springer , 2001. - ISBN 0-387-95220-9 .  — P. 3.
  2. ↑ Evstigneev V. A., Kasyanov V. N. . Dicționar de grafice în informatică. - Novosibirsk, 200. - (Proiectarea și optimizarea programelor, numărul 17). - ISBN 978-591124-036-3 .
  3. ↑ Moon J. W., Moser L.  On cliques in graphs // Israel Journal of Mathematics. - 1965. - Vol. 3, nr. 1. - P. 23–28. - doi : 10.1007/BF02760024 .
  4. ↑ Furedi, Zoltan. Numărul de mulțimi maxim independente din graficele conectate // Journal of Graph Theory. - 1987. - Vol. 11, nr. 4. - P. 463-470. - doi : 10.1002/jgt.3190110403 .
  5. ↑ Din articolul de mai jos al lui Rusov și Zakharova: Recent, algoritmii euristici, adică algoritmii care încă permit rezolvarea unei probleme NP-complete, dar cu o oarecare eroare, au fost de cel mai mare interes pentru rezolvarea acestui gen de probleme. Principalele criterii de evaluare a unui algoritm euristic sunt „eficiența în timp” și eroarea în raport cu algoritmul exact.
  6. ↑ Robson J. M.  Algorithms for maximum independent sets // Journal of Algorithms. - 1986. - Vol. 7, nr. 3. - P. 425-440. - doi : 10.1016/0196-6774(86)90032-5 .
  7. ↑ Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos, Johan M. M. van Rooij. . O metodă de jos în sus și algoritmi rapizi pentru MAX INDEPENDENT SET // Teoria algoritmului—SWAT 2010 . - Berlin: Springer , 2010. - (Lecture Notes in Computer Science, vol. 6139). - doi : 10.1007/978-3-642-13731-0_7 .  — P. 62–73.
  8. ↑ Chiba N., Nishizeki T.  Arboricity and subgraph listing algorithms // SIAM Journal on Computing . - 1985. - Vol. 14, nr. 1. - P. 210-223. - doi : 10.1137/0214017 .
  9. ↑ Piotr Berman, Toshihiro Fujito. . Despre proprietățile de aproximare ale problemei mulțimii independente pentru grafice de gradul 3 // Al patrulea atelier internațional de algoritmi și structuri de date. - Springer , 1995. - (Lecture Notes in Computer Science, vol. 995). - doi : 10.1007/3-540-60220-8_84 .  - P. 449-460.
  10. ↑ Halldórsson M. M., Radhakrishnan J.  Greed is good: Approximating independent sets in sparse and bounded-degree graphs // Algorithmica . - 1997. - Vol. 18, nr. 1. - P. 145-163. - doi : 10.1007/BF02523693 . .
  11. ↑ Sbihi, 1980 .
  12. ↑ Grötschel, Lovász, Schrijver, 1988 .
  13. ↑ Brenda S. Baker. Algoritmi de aproximare pentru probleme NP-complete pe grafice plane // Journal of the ACM . - 1994. - Vol. 41, nr. 1. - P. 153-180. - doi : 10.1145/174644.174650 .
  14. ↑ Martin Grohe. Lățimea arborelui local, minori excluși și algoritmi de aproximare // Combinatorica . - 2003. - Vol. 23, nr. 4. - P. 613-632. - doi : 10.1007/s00493-003-0037-9 .

Literatură

Link -uri

 Probleme NP-complete
Problema
de maximizare a stivuirii (ambalării)
teoria grafurilor
teoria multimelor
Probleme algoritmice
Jocuri de logică
și puzzle-uri