Faceți clic pe Lățime

În teoria grafurilor, lățimea clicei a unui graf  este un parametru care descrie complexitatea structurală a unui graf. Parametrul este strâns legat de treewidth , dar spre deosebire de treewidth, lățimea clicei poate fi limitată chiar și pentru grafice dense . Lățimea clicului este definită ca numărul minim de etichete necesare pentru a construi cu următoarele 4 operațiuni

  1. Crearea unui nou vârf v cu eticheta i ( operație i(v) )
  2. Unirea deconectată a două grafice etichetate G și H (operație )
  3. O conexiune de margine a fiecărui vârf cu eticheta i cu fiecare vârf cu eticheta j (operația η(i, j) ), unde
  4. Redenumiți eticheta i în j (operația ρ ( i , j ))

Graficele de lățime de clică delimitate includ cografe și grafice moștenite de distanță . Deși calcularea lățimii clicei este NP-hard , având în vedere că limita superioară nu este cunoscută și nu se știe dacă poate fi calculată în timp polinomial atunci când limita superioară este cunoscută, sunt cunoscuți algoritmi eficienți de aproximare pentru calcularea lățimii clicei. Pe baza acestor algoritmi și a teoremei lui Courcelle , multe probleme de optimizare pe grafice care sunt NP-hard pentru grafice arbitrare pot fi rezolvate sau aproximate rapid pentru grafice cu lățime limitată de clic.

Secvențele de construcție pe care se bazează noțiunea de lățime a clicei au fost formulate de Courcelle, Engelfried și Rosenberg în 1990 [1] și de Vanke [2] . Denumirea „click width” a fost folosită pentru un alt concept de Hlebikov [3] . Din 1993, termenul a fost folosit în sensul său modern [4] .

Clase speciale de grafice

Cografele  sunt exact grafice cu lățimea clicului de cel mult două [5] . Orice graf moștenit de distanță are o lățime de clic care nu depășește 3. Cu toate acestea, lățimea de clic a graficelor de interval nu este limitată (conform structurii rețelei) [6] . În mod similar, lățimea clicei a graficelor de permutare bipartite nu este limitată (conform structurii rețelei similare) [7] . Pe baza descrierii cografelor ca grafuri fără subgrafe generate izomorfe la căi fără coarde, lățimea clicei a multor clase de grafuri definite de subgrafe generate interzise a fost clasificată [8] [9] .

Alte grafice cu lățimea clicei mărginite sunt k - puteri ale frunzei pentru valorile mărginite ale lui k , adică subgrafe generate de frunze ale arborelui T la gradul graficului T k . Totuși, gradul frunzelor cu exponent nelimitat nu are o lățime limitată a frunzei [10] [11] .

Borduri

Courcelle și Olariu [5] , precum și Corneil și Rotix [12] , au dat următoarele limite pe lățimea clicei a unor grafice:

Mai mult, dacă graficul G are o lățime de clică k , atunci gradul graficului G c are o lățime de clică care nu depășește 2 kc k [18] . Deși există o exponențială în inegalitățile lățimii clicei în comparație cu lățimea copacului și gradul graficului, aceste limite nu dau o suprapunere - dacă graficul G are lățimea copacului w , atunci G c are o lățime a clicei de cel mult 2( c + 1) w + 1 − 2 , doar un simplu exponent al lățimii arborelui [11] .

Complexitate computațională

Probleme nerezolvate la matematică : Poate fi recunoscut un grafic cu lățimea clicei mărginite în timp polinomial?

Multe probleme de optimizare care sunt NP-hard pentru clase mai generale de grafice pot fi rezolvate eficient folosind programarea dinamică pe grafice cu lățimea clicei mărginite, dacă succesiunea de construire a acestor grafice este cunoscută [19] [20] . În special, orice invariant de grafic care poate fi exprimat în MSO 1 ( logica de ordinul doi cu un loc , un fel de logică de ordinul doi care permite cuantificatori peste seturi de vârfuri) are un algoritm de timp liniar pentru lățimea mărginită. grafice, prin una din formulările teoremei lui Courcelle [ 20] . De asemenea, se pot găsi colorări optime sau cicluri hamiltoniene ale graficelor cu lățimea clicei mărginite în timp polinomial dacă se cunoaște secvența de construcție a graficului, dar gradul polinomului crește cu lățimea clicei, iar argumentele din teoria complexității computaționale arată că o astfel de dependență pare să fie fi inevitabil [21] .

Graficele cu lățimea clicului trei pot fi recunoscute și secvența lor de construcție poate fi găsită în timp polinomial folosind un algoritm bazat pe descompunerea divizată [22] . Pentru clasele de grafice cu lățimea clicului nemărginit, calcularea lățimii clicei exacte este NP-hard și este, de asemenea, NP-greu să se obțină o aproximare cu eroare aditivă subliniară [23] . Totuși, dacă este cunoscută limita superioară a lățimii clicei, este posibil să se obțină o secvență de construcție a graficului cu o lățime mărginită (exponențial mai mare decât lățimea reală a clicei) în timp polinomial [17] [24] [25] . Rămâne o întrebare deschisă dacă lățimea exactă a clicei sau aproximarea apropiată poate fi calculată în timp fix-parametric rezolvabil , dacă poate fi calculată în timp polinomial pentru grafice cu orice limită fixă ​​a lățimii clicei sau chiar dacă graficele cu lățimea clicei. de lăţime patru sunt recunoscute în timp polinomial [23] .

Link către lățimea lemnului

Teoria grafurilor mărginite de lățime de clică are asemănări cu teoria grafurilor de lățime de arbore mărginită , dar, spre deosebire de lățimea arborelui, permite grafice dense . Dacă o familie de grafuri are o lățime de clică mărginită, atunci fie are lățime de arbore mărginită, fie orice graf bipartit complet este un subgraf al unui graf din familia [16] . Lățimea arborelui și lățimea clicei sunt, de asemenea, legate de teoria graficului liniare  - o familie de grafice are lățimea arborelui mărginită dacă și numai dacă graficele lor liniare au lățime mărginită a clicei [26] .

Note

  1. ↑ Courcelle, Engelfriet, Rozenberg, 1993 .
  2. ↑ Wanke, 1994 .
  3. ↑ Chlebíková, 1992 .
  4. ↑ Courcelle, 1993 .
  5. ↑ 12 Courcelle, Olariu, 2000 .
  6. ↑ Golumbic, Rotics, 2000 .
  7. ↑ Brandstädt, Lozin, 2003 .
  8. ↑ Brandstädt, Drăgan, Le, Mosca, 2005 .
  9. ↑ Brandstädt, Engelfriet, Le, Lozin, 2006 .
  10. ↑ Brandstädt, Hundt, 2008 .
  11. ↑ 12 Gurski , Wanke, 2009 .
  12. ↑ Corneil, Rotics, 2005 .
  13. ↑ Courcelle, Olariu, 2000 , p. Corolarul 3.3.
  14. ↑ Courcelle, Olariu, 2000 , p. Teorema 4.1.
  15. ↑ Corneil, Rotics, 2005 , Întărirea - Courcelle, Olariu, 2000 , Teorema 5.5.
  16. ↑ 12 Gurski , Wanke, 2000 .
  17. ↑ 12 Oum , Seymour, 2006 .
  18. ↑ Todinca, 2003 .
  19. ↑ Cogis, Thierry, 2005 .
  20. ↑ 12 Courcelle, Makowsky, Rotics, 2000 .
  21. ↑ Fomin, Golovach, Lokshtanov, Saurabh, 2010 .
  22. ↑ Cornel at al, 2012 .
  23. ↑ 1 2 Fellows, Rosamond, Rotics, Szeider, 2009 .
  24. ↑ Hliněny, Oum, 2008 .
  25. ↑ Oum, 2009 .
  26. ↑ Gurski, Wanke, 2007 .

Literatură