Klikkszélesség

A matematika, azon belül a gráfelmélet területén egy gráf klikkszélessége (clique-width) a gráf szerkezetének bonyolultságát leíró paraméter; közeli rokona a faszélességnek, de attól eltérő módon, sűrű gráfokon is korlátos lehet az értéke. A definíció szerint értéke megegyezik a ${\displaystyle G}$ gráf konstruálásához szükséges címkék minimális számával, ha a következő négy művelet engedélyezett:

1. Felveszünk egy új csúcsot, v-t és i címkével látjuk el (jelölés: i(v) vagy ${\displaystyle \bullet _{i}}$)
2. Két címkézett gráf, G és H diszjunkt unióját képezzük (jelölés: ${\displaystyle G\oplus H}$)
3. Minden i-vel jelölt csúcsot összekötünk minden j-vel jelölt csúccsal (jelölés: η(i,j)), ahol ${\displaystyle i\neq j}$
4. Átnevezzük az i címkét j-re (jelölés: ρ(i,j) )

Egy 3 klikkszélességű távolság-örökletes gráf konstrukciója diszjunkt uniókkal, átcímkézésekkel és címke-egyesítésekkel. A címkéket az ábrán színek jelzik.

A korlátos klikkszélességű gráfok közé tartoznak a kográfok és a távolság-örökletes gráfok is. Bár általános esetben a klikkszélesség meghatározása NP-nehéz feladat, és nem tudjuk, vajon polinom időben kiszámítható-e abban az esetben, ha korlátos, ismert több hatékony közelítő algoritmus a klikkszélesség kiszámítására. Ezekre az algoritmusokra és a Courcelle-tételre alapozva számos, általános gráfokon NP-nehéz gráfoptimalizálási probléma gyorsan megoldható vagy közelíthető a korlátos klikkszélességű gráfokon.

A klikkszélesség fogalmához szükséges konstrukciós lépéseket Courcelle, Engelfriet és Rozenberg fogalmazta meg 1990-ben ^[1], majd (Wanke 1994). A „klikkszélesség” kifejezést először (Chlebíková 1992) használta egy másik fogalom leírására, de 1993-ra már a jelenlegi értelemben használták.^[2]

Példa

A ${\displaystyle C_{6}}$ konstrukciós lépéseinek kifejezés-fája

A 6 csúcsból álló ${\displaystyle C_{6}}$ gráf klikkszélessége nem nagyobb 3-nál, mivel a következő műveletek segítségével előállítható:

Klikkszélesség-művelet	A gráf vizualizációja
${\displaystyle G_{1}=\bullet _{1}}$
${\displaystyle G_{2}=\bullet _{2}}$
${\displaystyle G_{3}=G_{1}\oplus G_{2}}$
${\displaystyle G_{4}=\eta _{1,2}(G_{3})}$
${\displaystyle G_{5}=G_{4}\oplus G_{4}}$
${\displaystyle G_{6}=G_{5}\oplus \bullet _{3}}$
${\displaystyle G_{7}=\eta _{1,3}(G_{6})}$
${\displaystyle G_{8}=\rho _{3\rightarrow 1}(G_{7})}$
${\displaystyle G_{9}=G_{8}\oplus \bullet _{3}}$
${\displaystyle C_{6}=\eta _{2,3}(G_{9})}$

Az előállított ${\displaystyle 3}$-művelet a következő:

${\displaystyle X=\eta _{2,3}(\rho _{3\rightarrow 1}(\eta _{1,3}(\eta (\bullet _{1}\oplus \bullet _{2})\oplus \eta (\bullet _{1}\oplus \bullet _{2})\oplus \bullet _{3}))\oplus \bullet _{3})}$

A jobb oldalon látható az ${\displaystyle X}$ 3-kifejezés fája.

Speciális gráfosztályok

A kográfok megegyeznek azokkal a gráfokkal, melyek klikkszélessége legfeljebb 2.^[3] A távolság-örökletes gráfok klikkszélessége legfeljebb 3. Az egység-intervallumgráfok klikkszélessége azonban (rácsos szerkezetük miatt) korlátlan.^[4] Hasonlóan, a páros permutációgráfok klikkszélessége (hasonlóan a rácsos szerkezet maitt) korlátlan.^[5] A kográfok egyik karakterizálása szerint ezek a gráfok, melyeknek nincs négy csúcsból álló húrmentes úttal izomorf feszített részgráfja. Ebből kiindulva számos, tiltott feszített részgráfok alapján meghatározott gráfcsalád klikkszélességét sikerült megállapítani.^[6]

A korlátos klikkszélességű gráfok közé tartoznak még a k-adik levélhatványok is a k korlátos értékeire; ezek a T^k gráfhatvány T levelei által kifeszített részgráfjai. A nem korlátos kitevőjű levélhatványok esetében azonban a klikkszélesség sem korlátos.^[7]

Korlátok

(Courcelle & Olariu 2000) és (Corneil & Rotics 2005) egyes gráfok klikkszélességével kapcsolatban a következőket igazolták:

• Ha egy gráf klikkszélessége legfeljebb k, akkor ez igaz a gráf minden feszített részgráfjára is.^[8]
• Egy k klikkszélességű gráf komplementerének klikkszélessége legfeljebb 2k.^[9]
• A w faszélességű gráfok klikkszélessége legfeljebb 3 · 2^{w − 1}. A korlátban szereplő exponenciális tag szükséges: ténylegesen léteznek olyan gráfok, melyek klikkszélessége exponenciálisan nagyobb a faszélességüknél.^[10] Megfordítva, a korlátos klikkszélességű gráfok rendelkezhetnek korlátlan faszélességgel; például az n csúcsú teljes gráfok klikkszélessége 2, míg faszélességük n − 1. Azoknak a k klikkszélességű gráfoknak viszont, melyek nem tartalmazzák a K_t,t teljes páros gráfot részgráfként, legfeljebb 3k(t − 1) − 1 lehet a faszélességük. Így aztán, tetszőleges ritka gráfcsaládra igaz, hogy a korlátos faszélesség ekvivalens a korlátos klikkszélességgel.^[11]
• Egy további gráfparamétert, a rangszélességet (rank-width) mindkét irányból korlátok közé szorít a klikkszélesség: rangszélesség ≤ klikkszélesség ≤ 2^{rangszélesség + 1}.^[12]

Igaz továbbá, hogy ha a G gráf klikkszélessége k, akkor a G^c gráfhatvány klikkszélessége legfeljebb 2kc^k.^[13] Bár mind a klikkszélesség a faszélesség szerinti korlátjában, mind klikkszélesség gráfhatvány szerinti korlátjában exponenciális rés szerepel, ezeknek a korlátok nem szorzódnak össze: ha a G gráf faszélessége w, akkor G^c klikkszélessége legfeljebb 2(c + 1)^{w + 1} − 2, ami a faszélességnek csak egyszeresen exponenciális függvénye.^[14]

Számítási bonyolultság

A matematika megoldatlan problémája: Felismerhetők-e polinom időben a korlátos klikkszélességű gráfok? (A matematika további megoldatlan problémái)

Számos, általánosabb gráfosztályokon NP-nehéz optimalizálási probléma korlátos klikkszélességű gráfokon dinamikus programozás segítségével hatékonyan megoldható, ha ezen gráfok konstrukciós lépései ismertek.^[15][16] Közelebbről, minden gráftulajdonság, aminek létezése kifejezhető a gráftulajdonságokat logikai műveletekkel, kvantorokkal stb. leíró MSO₁ monadikus másodrendű logika segítségével, a Courcelle-tétel egy változata alapján lineáris idejű algoritmussal eldönthető.^[16]

Polinom időben lehetséges továbbá a korlátos klikkszélességű gráfok optimális gráfszínezését és Hamilton-körét megtalálni, ha a konstrukciós lépések ismertek, de a polinom kitevője a klikkszélességgel növekszik, és a számítási bonyolultságelmélet bizonyítékai arra mutatnak, hogy ettől a függőségtél valószínűleg nem lehet eltekinteni.^[17] A korlátos klikkszélességű gráfok χ-korlátosak, vagyis kromatikus számuk legfeljebb a legnagyobb klikk méretének függvénye lehet.^[18]

A három klikkszélességű gráfok polinom időben felismerhetők, és konstrukciós lépéseik is előállíthatók egy splitfelbontás-alapú algoritmussal.^[19] A nem korlátos klikkszélességű gráfok esetén NP-nehéz a klikkszélesség pontos megállapítása, ahogy a szublineáris additív hibával történő approximációja is.^[20] Ha azonban a klikkszélesség korlátos, egy korlátos szélességű (exponenciálisan nagyobb mint a tényleges klikkszélesség) konstrukciós lépéssorozat polinom időben előállítható.^[21] Nyitott egyelőre az a kérdés, hogy a pontos klikkszélesség, vagy akár egy pontosabb approximációja kiszámítható-e rögzített paraméter mellett kezelhető időben, polinom időben kiszámítható-e minden rögzített klikkszélesség-korlát esetén, vagy akár a négy klikkszélességű gráfok felismerhetők-e a polinom időben.^[20]

Faszélességgel való kapcsolata

A korlátos klikkszélességű gráfok elmélete hasonlít a korlátos faszélességű gráfokéhoz, de azoktól eltérően sűrű gráfokkal is foglalkozik. Ha egy gráfcsalád klikkszélessége korlátos, akkor vagy a faszélessége is korlátos, vagy minden teljes páros gráf a család valamely tagjának részgráfja.^[11] A faszélesség és a klikkszélesség az élgráfokon keresztül is összekapcsolódik: egy gráfcsalád pontosan akkor korlátos faszélességű, ha élgráfjaiknak klikkszélessége korlátos.^[22]

Fordítás

• Ez a szócikk részben vagy egészben a Clique-width című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

1. Courcelle, Engelfriet & Rozenberg (1993).
2. Courcelle (1993).
3. Courcelle & Olariu (2000).
4. Golumbic & Rotics (2000).
5. Brandstädt & Lozin (2003).
6. (Brandstädt et al. 2005); (Brandstädt et al. 2006).
7. (Brandstädt & Hundt 2008); (Gurski & Wanke 2009).
8. (Courcelle & Olariu 2000), Corollary 3.3.
9. (Courcelle & Olariu 2000), Theorem 4.1.
10. (Corneil & Rotics 2005), megerősítve (Courcelle & Olariu 2000), Theorem 5.5-jét.
11. Gurski & Wanke (2000).
12. Oum & Seymour (2006).
13. Todinca (2003).
14. Gurski & Wanke (2009).
15. Cogis & Thierry (2005).
16. Courcelle, Makowsky & Rotics (2000).
17. Fomin et al. (2010).
18. Dvořák & Král' (2012).
19. Corneil et al. (2012).
20. Fellows et al. (2009).
21. (Oum & Seymour 2006); (Hliněný & Oum 2008); (Oum 2009).
22. Gurski & Wanke (2007).

• .
• .
• .
• .
• .
• .
• .
• .
• . Presented in preliminary form in Graph grammars and their application to computer science (Bremen, 1990), MR1431281.
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .