Kattintson a Szélesség elemre

A gráfelméletben a gráf klikkszélessége  egy olyan paraméter, amely leírja a gráf szerkezeti összetettségét. A paraméter szorosan kapcsolódik a treewidth -hez , de a treewidth-től eltérően a klikk szélessége még sűrű gráfok esetén is korlátozható . A kattintási szélesség a következő 4 művelettel történő felépítéshez szükséges címkék minimális száma

  1. Új v csúcs létrehozása i címkével ( i(v) művelet )
  2. Két címkézett G és H gráf szétválasztott egyesítése ( művelet )
  3. Minden i címkés csúcs élkapcsolata minden j címkés csúcsgal ( η(i, j) művelet ), ahol
  4. Az i címke átnevezése j-re ( ρ ( i , j ) művelet )

A korlátos kattintásszélességű grafikonok magukban foglalják a kográfokat és a távolságtól örökölt grafikonokat . Bár a klikk szélességének kiszámítása NP-nehéz , mivel a felső korlát nem ismert, és nem ismert, hogy kiszámítható-e polinomiális időben, ha a felső korlát ismert, ismertek hatékony közelítő algoritmusok a klikk szélességének kiszámítására. Ezen algoritmusok és a Courcelle-tétel alapján számos optimalizálási probléma olyan gráfokon, amelyek NP-nehézek tetszőleges gráfokhoz, gyorsan megoldható vagy közelíthető korlátozott klikkszélességű gráfok esetén.

A klikkszélesség fogalmának alapjául szolgáló konstrukciós sorozatokat Courcelle, Engelfried és Rosenberg 1990-ben [1] és Vanke [2] fogalmazta meg . A "kattintásszélesség" elnevezést egy másik fogalomra használta Hlebikov [3] . 1993 óta a kifejezést a mai értelemben használjuk [4] .

A gráfok speciális osztályai

A kográfok  pontosan olyan gráfok, amelyek kattintásának szélessége legfeljebb kettő [5] . Bármely távolság-örökölt gráf klikkszélessége nem haladja meg a 3-at. Az intervallumgráfok klikkszélessége azonban nincs korlátozva (a rácsszerkezet szerint) [6] . Hasonlóképpen, a kétrészes permutációs gráfok klikkszélessége nincs korlátozva (a hasonló rácsszerkezetnek megfelelően) [7] . A kográfok generált részgráfok nélküli gráfokként való leírása alapján, amelyek izomorfak az akkord nélküli útvonalakkal, a tiltott generált részgráfok által meghatározott gráfok számos osztályának klikkszélességét osztályozták [8] [9] .

Más korlátos klikkszélességű grafikonok k - levél hatványok k korlátos értékeire , vagyis a T fa leveleinek generált részgráfjai a T k gráf fokára . A korlátlan kitevővel rendelkező levelek fokának azonban nincs korlátozott levélszélessége [10] [11] .

Szegélyek

Courcelle és Olariu [5] , valamint Corneil és Rotix [12] a következő korlátokat adta meg néhány gráf klikkszélességére:

Sőt, ha a G gráf klikkszélessége k , akkor a G c gráf fokszáma legfeljebb 2 kc k klikkszélességű [18] . Bár a gráf faszélességével és fokszámával összehasonlítva exponenciális a klikkszélesség-egyenlőtlenségek, ezek a korlátok nem adnak szuperpozíciót – ha a G gráf faszélessége w , akkor G c klikkszélessége legfeljebb 2( c + 1) w + 1 − 2 , csak a fa szélességének egyszerű kitevője [11] .

Számítási összetettség

Megoldatlan problémák a matematikában : Felismerhető-e egy korlátos klikkszélességű gráf polinomiális időben?

Számos olyan optimalizálási probléma, amely NP-nehéz a gráfok általánosabb osztályaihoz, hatékonyan megoldható dinamikus programozással korlátos klikkszélességű gráfokon, ha ismert a gráfok felépítésének sorrendje [19] [20] . Konkrétan minden gráfinvariáns , amely kifejezhető az MSO 1 -ben ( egyhelyű másodrendű logika , egyfajta másodrendű logika, amely lehetővé teszi a kvantorokat csúcshalmazok felett) rendelkezik egy lineáris idejű algoritmussal a korlátos szélességhez. gráfok, a Courcelle-tétel [20] egyik megfogalmazásával . Megtalálható a korlátos klikkszélességű gráfok optimális színezése vagy Hamilton -ciklusa is polinomidőben, ha ismert a gráf felépítési sorrendje, de a polinom mértéke a klikk szélességének növekedésével növekszik, és a számítási komplexitás elméletéből származó érvek azt mutatják, hogy ez a függés elkerülhetetlen legyen [21] .

A hármas klikkszélességű gráfok felismerhetők és szerkesztési sorrendjük polinomiális időben megkereshető egy osztott dekompozíción alapuló algoritmus [22] segítségével . A korlátlan klikkszélességű gráfok osztályainál a pontos klikkszélesség kiszámítása NP-nehéz , valamint NP-nehéz közelítést kapni szublineáris additív hibával [23] . Ha azonban ismert a klikk szélességének felső korlátja, akkor polinomiális idő alatt korlátos szélességű (exponenciálisan nagyobb, mint a klikk szélessége exponenciálisan nagyobb) gráfépítési sorozatot kaphatunk [17] [24] [25] . Nyitott kérdés marad, hogy a pontos klikkszélesség vagy közeli közelítés kiszámítható-e fix-parametrikusan feloldható időben, kiszámítható-e polinomiális időben bármilyen fix klikkszélességhez kötött gráf esetén, vagy akár a klikk szélességű gráfok esetében is. négyes szélességűek polinomiális időben kerülnek felismerésre [23] .

Link a faszélességhez

A korlátos kattintásszélességű gráfelmélet hasonlóságokat mutat a korlátos faszélességű gráfelmélettel , de a faszélességtől eltérően sűrű gráfokat tesz lehetővé . Ha egy gráfcsaládnak korlátos klikkszélessége van, akkor vagy korlátos a faszélessége, vagy bármely teljes bipartit gráf a család valamelyik gráfjának részgráfja [16] . A fa szélességét és a klikk szélességét a vonalgráf- elmélet is összefügg – egy gráfcsaládnak  akkor és csak akkor van határos faszélessége, ha a vonalgráfjaik korlátos klikkszélességgel rendelkeznek [26] .

Jegyzetek

  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, Dragan, 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. Következmény 3.3.
  14. ↑ Courcelle, Olariu, 2000 , p. 4.1. Tétel.
  15. ↑ Corneil, Rotics, 2005 , Erősítés - Courcelle, Olariu, 2000 , 5.5. Tétel.
  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, Szaurabh, 2010 .
  22. ↑ Corneil és mtsai, 2012 .
  23. ↑ 1 2 Fellows, Rosamond, Rotics, Szeider, 2009 .
  24. ↑ Hliněny, Oum, 2008 .
  25. ↑ Ó, 2009 .
  26. ↑ Gurski, Wanke, 2007 .

Irodalom