Klickbredd

Konstruktion av ett ärftligt avståndsdiagram med klickbredd 3 genom osammanhängande kopplingar, ommärkningar och etikettfogar. Vertexetiketter visas som färger.

I grafteori är klickbredden på en graf G en parameter som beskriver grafens strukturella komplexitet ; den är nära relaterad till trädbredden , men till skillnad från trädbredden kan den avgränsas även för täta grafer . Det definieras som det minsta antalet etiketter som behövs för att konstruera G med hjälp av följande 4 operationer:

  1. Skapande av en ny vertex v med etikett i (betecknad med i ( v ) )
  2. Disjunkt förening av två märkta grafer G och H (betecknas med )
  3. Sammanfoga med en kant varje vertex märkt i med varje vertex märkt j (betecknad med η ( i , j ) ), där i ≠ j
  4. Byter namn på etikett i till etikett j (betecknas med ρ ( i , j ) )

Grafer med avgränsad klickbredd inkluderar kografer och ärftliga avståndsgrafer . Även om det är NP-svårt att beräkna klickbredden när den är obegränsad, och okänt om den kan beräknas i polynomtid när den är begränsad, är effektiva approximationsalgoritmer för klickbredd kända. Baserat på dessa algoritmer och på Courcelles teorem kan många grafoptimeringsproblem som är NP-svåra för godtyckliga grafer lösas eller approximeras snabbt på graferna med begränsad klickbredd.

Konstruktionssekvenserna som ligger till grund för begreppet klickbredd formulerades av Courcelle , Engelfriet och Rozenberg 1990 och av Wanke (1994) . Namnet "klickbredd" användes för ett annat koncept av Chlebíková (1992) . Redan 1993 hade termen sin nuvarande betydelse.

Särskilda klasser av grafer

Kografer är exakt de grafer med klickbredd som högst 2. Varje ärftlig avståndsgraf har klickbredd högst 3. Klickbredden för grafer med enhetsintervall är dock obegränsad (baserat på deras rutnätsstruktur). På liknande sätt är klickbredden för tvådelade permutationsgrafer obegränsad (baserat på liknande rutnätsstruktur). Baserat på karakteriseringen av kografer som graferna utan inducerad subgraf som är isomorfa till en bana med fyra hörn, har klickbredden för många grafklasser som definieras av förbjudna inducerade subgrafer klassificerats.

Andra grafer med begränsad klickbredd inkluderar k -bladpotenserna för avgränsade värden av k ; dessa är de inducerade subgraferna av bladen på ett träd T i grafens potens T k . Bladpotenser med obundna exponenter har dock inte begränsad klickbredd.

Gräns

Courcelle & Olariu (2000) och Corneil & Rotics (2005) bevisade följande gränser för klickbredden för vissa grafer:

  • Om en graf har högst klickbredd k , så har varje inducerad subgraf i grafen det.
  • Komplementgrafen för en graf med klickbredd k har klickbredd högst 2 k .
  • Graferna för trädbredden w har högst klickbredd 3 · 2 w − 1 . Det exponentiella beroendet i denna gräns är nödvändigt: det finns grafer vars klickbredd är exponentiellt större än deras trädbredd. I den andra riktningen kan grafer med begränsad klickbredd ha obegränsad trädbredd; till exempel n -vertex kompletta grafer klickbredd 2 men trädbredd n − 1 . Emellertid har grafer med klickbredd k som inte har någon fullständig tvådelad graf K t , t som en subgraf trädbredden högst 3 k ( t − 1) − 1 . Därför, för varje familj av glesa grafer , är det att ha avgränsad trädbredd likvärdigt med att ha avgränsad klickbredd.
  • En annan grafparameter, rank-width , begränsas i båda riktningarna av klickbredden: rank-width ≤ clique-width ≤ 2 rank-width + 1 .

Gc Dessutom , om en graf G har klickbredd k , så har grafeffekten klickbredd högst 2 kc k . Även om det finns ett exponentiellt gap Gc i både gränsen för klickbredd från trädbredden och gränsen för klickbredd för grafpotenser, sammanbinder dessa gränser inte varandra: om en graf G har trädbredden w , så har klickbredden högst 2( c + 1) w + 1 − 2 , endast exponentiellt enstaka i trädbredden.

Beräkningskomplexitet

Olöst problem i matematik :

Kan grafer med begränsad klickbredd kännas igen i polynomtid?

(fler olösta problem i matematik)

Många optimeringsproblem som är NP-svåra för mer generella klasser av grafer kan lösas effektivt genom dynamisk programmering på grafer med begränsad klickbredd, när en konstruktionssekvens för dessa grafer är känd. I synnerhet har varje grafegenskap som kan uttryckas i MSO 1 monadisk andra ordningens logik (en form av logik som tillåter kvantifiering över uppsättningar av hörn) en linjär-tidsalgoritm för grafer med begränsad klickbredd, av en form av Courcelles teorem .

Det är också möjligt att hitta optimala graffärger eller Hamiltons cykler för grafer med begränsad klickbredd i polynomtid, när en konstruktionssekvens är känd, men exponenten för polynomet ökar med klickbredden, och bevis från beräkningskomplexitetsteori visar att detta beroende sannolikt är nödvändigt. Graferna för den begränsade klickbredden är χ -begränsade , vilket betyder att deras kromatiska nummer som mest är en funktion av storleken på deras största klick.

Graferna för klickbredd tre kan kännas igen, och en konstruktionssekvens hittas för dem, i polynomtid med hjälp av en algoritm baserad på delad uppdelning . För grafer med obegränsad klickbredd är det NP-svårt att beräkna klickbredden exakt, och även NP-svårt att få en approximation med sublinjärt additivt fel. Men när klickbredden är begränsad är det möjligt att erhålla en konstruktionssekvens av begränsad bredd (exponentiellt större än den faktiska klickbredden) i polynomtid, i synnerhet i kvadratisk tid i antalet hörn. Det förblir öppet om den exakta klickbredden, eller en snävare approximation till den, kan beräknas i traktbar tid med fasta parametrar, om den kan beräknas i polynomtid för varje fast gräns på klickbredden, eller till och med om graferna av klickbredd fyra kan kännas igen i polynomtid.

Relaterade breddparametrar

Teorin om grafer med begränsad klickbredd liknar den för grafer med begränsad trädbredd , men till skillnad från trädbredd tillåter täta grafer . Om en familj av grafer har avgränsad klickbredd, så har den antingen en gräns trädbredd eller så är varje komplett tvådelad graf en subgraf till en graf i familjen. Trädbredd och klickbredd är också sammankopplade genom teorin om linjegrafer : en familj av grafer har avgränsad trädbredd om och endast om deras linjegrafer har avgränsad klickbredd.

Graferna för begränsad klickbredd har också begränsad tvillingbredd .

Anteckningar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Clique-width&oldid=1136151182 "