Klicka på Bredd

I grafteorin är klickbredden på en graf  en parameter som beskriver en grafs strukturella komplexitet. Parametern är nära relaterad till treewidth , men till skillnad från treewidth kan klickbredden begränsas även för täta grafer . Klickbredd definieras som det minsta antal etiketter som krävs för att bygga med följande 4 operationer

  1. Skapa en ny vertex v med etikett i ( i(v) operation )
  2. Frånkopplad förening av två märkta grafer G och H (drift )
  3. En kantförbindelse av varje vertex med etikett i med varje vertex med etikett j (operation η(i, j) ), där
  4. Byt namn på etikett i till j (operation ρ ( i , j ))

Avgränsade klickbreddsgrafer inkluderar kografer och avståndsärvda grafer . Även om beräkning av klickbredden är NP-hård , med tanke på att den övre gränsen inte är känd och det inte är känd om den kan beräknas i polynomtid när den övre gränsen är känd, är effektiva approximationsalgoritmer för att beräkna klickbredden kända. Baserat på dessa algoritmer och Courcelles teorem kan många optimeringsproblem på grafer som är NP-hårda för godtyckliga grafer lösas eller approximeras snabbt för grafer med begränsad klickbredd.

De konstruktionssekvenser som begreppet klickbredd bygger på formulerades av Courcelle, Engelfried och Rosenberg 1990 [1] och av Vanke [2] . Namnet "klickbredd" användes för ett annat koncept av Khlebikov [3] . Sedan 1993 har termen använts i sin moderna betydelse [4] .

Särskilda klasser av grafer

Cographs  är exakt grafer med klickbredd som högst två [5] . Varje avståndsärvd graf har en klickbredd som inte överstiger 3. Klickbredden för intervallgrafer är dock inte begränsad (enligt gitterstrukturen) [6] . På liknande sätt är klickbredden för tvådelade permutationsgrafer inte begränsad (enligt den liknande gitterstrukturen) [7] . Baserat på beskrivningen av kografer som grafer utan genererade subgrafer som är isomorfa till banor utan ackord, klassificerades klickbredden för många klasser av grafer som definieras av förbjudna genererade subgrafer [8] [9] .

Andra grafer med avgränsad klickbredd är k - bladpotenser för avgränsade värden av k , det vill säga genererade subgrafer av löv på trädet T till graden av grafen T k . Graden av löv med en obegränsad exponent har dock inte en begränsad lövbredd [10] [11] .

Gränser

Courcelle och Olariu [5] , liksom Corneil och Rotix [12] , gav följande gränser för klickbredden på några grafer:

Dessutom, om grafen G har en klickbredd k , så har graden av grafen Gc en klickbredd som inte överstiger 2 kc k [18] . Även om det finns en exponentiell ojämlikhet i klickbredden i jämförelse med trädets bredd och grad av grafen, ger dessa gränser ingen superposition – om grafen G har trädbredden w , så har G c en klickbredd på högst 2( c + 1) w + 1 − 2 , bara en enkel exponent för trädets bredd [11] .

Beräkningskomplexitet

Olösta problem i matematik : Kan en graf med begränsad klickbredd kännas igen i polynomtid?

Många optimeringsproblem som är NP-svåra för mer allmänna klasser av grafer kan lösas effektivt med dynamisk programmering på grafer med begränsad klickbredd, om sekvensen för att konstruera dessa grafer är känd [19] [20] . Speciellt alla grafinvarianter som kan uttryckas i MSO 1 ( en -plats andra ordningens logik , en sorts andra ordningens logik som tillåter kvantifierare över uppsättningar av hörn) har en linjär-tidsalgoritm för avgränsad bredd grafer, genom en av formuleringarna av Courcelles sats [20] . Man kan också hitta optimala färgningar eller Hamiltonska cykler av gränsade klickbreddsgrafer i polynomtid om grafens konstruktionssekvens är känd, men graden av polynomet ökar med klickbredden, och argument från beräkningskomplexitetsteorin visar att ett sådant beroende verkar vara vara oundviklig [21] .

Grafer med klickbredd tre kan kännas igen och deras konstruktionssekvens kan hittas i polynomtid med hjälp av en algoritm baserad på delad uppdelning [22] . För klasser av grafer med obegränsad klickbredd är det NP-hårt att beräkna den exakta klickbredden , och det är också NP-svårt att få en approximation med sublinjärt additivfel [23] . Men om den övre gränsen för klickbredden är känd är det möjligt att få en grafkonstruktionssekvens med en begränsad bredd (exponentiellt större än den faktiska klickbredden) i polynomtid [17] [24] [25] . Det är fortfarande en öppen fråga om den exakta klickbredden eller nära approximationen kan beräknas i fast-parametriskt upplösbar tid, om den kan beräknas i polynomtid för grafer med någon fast klickbredd bunden, eller till och med om grafer med klickbredd av bredd fyra känns igen i polynomtid [23] .

Länk till vedens bredd

Begränsad klickbreddsgrafteori har likheter med gränsad trädbreddsgrafteori , men till skillnad från trädbredd tillåter den täta grafer . Om en familj av grafer har avgränsad klickbredd, så har den antingen en begränsad trädbredd, eller så är vilken komplett tvådelad graf som helst en subgraf till någon graf i familjen [16] . Trädbredd och klickbredd är också relaterade till linjegrafteori  - en familj av grafer har en begränsad trädbredd om och endast om deras linjegrafer har en gränsad klickbredd [26] .

Anteckningar

  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 , sid. Följd 3.3.
  14. ↑ Courcelle, Olariu, 2000 , sid. Sats 4.1.
  15. ↑ Corneil, Rotics, 2005 , Strengthening - Courcelle, Olariu, 2000 , Theorem 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. ↑ Corneil et al, 2012 .
  23. ↑ 1 2 Fellows, Rosamond, Rotics, Szeider, 2009 .
  24. ↑ Hliněny, Oum, 2008 .
  25. ↑ Oum, 2009 .
  26. ↑ Gurski, Wanke, 2007 .

Litteratur