Klik på Bredde

I grafteori er klikbredden af ​​en graf  en parameter, der beskriver den strukturelle kompleksitet af en graf. Parameteren er tæt forbundet med treewidth , men i modsætning til treewidth kan klikbredden begrænses selv for tætte grafer . Klikbredde er defineret som det mindste antal etiketter, der kræves for at bygge med de følgende 4 operationer

  1. Oprettelse af et nyt vertex v med label i ( i(v) operation )
  2. Afbrudt forening af to mærkede grafer G og H (drift )
  3. En kantforbindelse af hvert toppunkt med label i med hvert toppunkt med label j (operation η(i, j) ), hvor
  4. Omdøb etiket i til j (operation ρ ( i , j ))

Afgrænsede klikbreddegrafer inkluderer kografer og afstandsarvede grafer . Selvom beregningen af ​​klikebredden er NP-hård , da den øvre grænse ikke er kendt, og det ikke vides, om den kan beregnes i polynomiel tid, når den øvre grænse er kendt, kendes effektive tilnærmelsesalgoritmer til beregning af klikbredden. Baseret på disse algoritmer og Courcelles teorem kan mange optimeringsproblemer på grafer, der er NP-hårde for vilkårlige grafer, løses eller tilnærmes hurtigt for grafer med begrænset klikbredde.

De konstruktionssekvenser, som forestillingen om klikebredde bygger på, blev formuleret af Courcelle, Engelfried og Rosenberg i 1990 [1] og af Vanke [2] . Navnet "klikbredde" blev brugt til et andet koncept af Khlebikov [3] . Siden 1993 er udtrykket blevet brugt i sin moderne betydning [4] .

Særlige klasser af grafer

Cographs  er præcis grafer med klikbredde højst to [5] . Enhver afstandsarvet graf har en klikbredde, der ikke overstiger 3. Klikebredden af ​​intervalgrafer er dog ikke begrænset (i henhold til gitterstrukturen) [6] . Tilsvarende er klikbredden af ​​todelte permutationsgrafer ikke begrænset (i henhold til den lignende gitterstruktur) [7] . Baseret på beskrivelsen af ​​kografer som grafer uden genererede subgrafer, der er isomorfe til stier uden akkorder, blev klikbredden af ​​mange klasser af grafer defineret af forbudte genererede subgrafer klassificeret [8] [9] .

Andre grafer med afgrænset klikbredde er k - bladpotenser for afgrænsede værdier af k , det vil sige genererede undergrafer af blade af træet T til graden af ​​grafen T k . Men graden af ​​blade med en ubegrænset eksponent har ikke en begrænset bladbredde [10] [11] .

Grænser

Courcelle og Olariu [5] , samt Corneil og Rotix [12] , gav følgende grænser for klikbredden af ​​nogle grafer:

Desuden, hvis grafen G har en klikbredde k , så har graden af ​​grafen Gc en klikbredde , der ikke overstiger 2 kc k [18] . Selvom der er en eksponentiel i klikbredde-ulighederne i sammenligning med træets bredde og grad af grafen, giver disse grænser ikke en superposition - hvis grafen G har træbredden w , så har G c en klikbredde på højst 2( c + 1) w + 1 − 2 , blot en simpel eksponent for træets bredde [11] .

Beregningsmæssig kompleksitet

Uløste problemer i matematik : Kan en graf med afgrænset klikbredde genkendes i polynomisk tid?

Mange optimeringsproblemer, der er NP-hårde for mere generelle klasser af grafer, kan løses effektivt ved hjælp af dynamisk programmering på grafer med afgrænset klikbredde, hvis sekvensen for at konstruere disse grafer er kendt [19] [20] . Især har enhver grafinvariant , der kan udtrykkes i MSO 1 ( en -steds andenordens logik , en slags andenordens logik, der tillader kvantifiers over sæt af hjørnepunkter) en lineær-tidsalgoritme for afgrænset bredde grafer, ved en af ​​formuleringerne af Courcelles sætning [20] . Man kan også finde optimale farvelægninger eller Hamiltonske cyklusser af afgrænsede klikbreddegrafer i polynomiel tid, hvis grafens konstruktionssekvens er kendt, men graden af ​​polynomiet stiger med klikbredden, og argumenter fra beregningsmæssig kompleksitetsteori viser, at en sådan afhængighed synes at være uundgåelig [21] .

Grafer med klikebredde tre kan genkendes, og deres konstruktionssekvens kan findes i polynomisk tid ved hjælp af en algoritme baseret på split dekomponering [22] . For klasser af grafer med ubegrænset klikbredde er beregning af den nøjagtige klikbredde NP-hård , og det er også NP-svært at opnå en tilnærmelse med sublineær additiv fejl [23] . Men hvis den øvre grænse for klikebredden er kendt, er det muligt at opnå en grafkonstruktionssekvens med en afgrænset bredde (eksponentielt større end den faktiske klikbredde) i polynomiel tid [17] [24] [25] . Det er stadig et åbent spørgsmål, om den nøjagtige klikbredde eller tætte tilnærmelse kan beregnes i fast-parametrisk opløselig tid, om den kan beregnes i polynomiel tid for grafer med en hvilken som helst fast klikbredde bundet, eller endda om grafer med klikbredde af bredde fire genkendes i polynomiel tid [23] .

Link til træbredde

Bounded clique-width-grafteori har ligheder med bounded tree-width- grafteori , men tillader i modsætning til træbredde tætte grafer . Hvis en familie af grafer har afgrænset klikbredde, så har den enten afgrænset træbredde, eller enhver komplet todelt graf er en undergraf til en graf i familien [16] . Træbredde og klikbredde er også forbundet med linjegrafteori  - en familie af grafer har afgrænset træbredde, hvis og kun hvis deres linjegrafer har afgrænset klikbredde [26] .

Noter

  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 , s. Konsekvens 3.3.
  14. ↑ Courcelle, Olariu, 2000 , s. Sætning 4.1.
  15. ↑ Corneil, Rotics, 2005 , Strengthening - Courcelle, Olariu, 2000 , Sætning 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