Klickomslag

I grafteorin är ett klicktäcke eller en uppdelning i klick av en given oriktad graf en uppdelning av hörnen i klicker , delmängder av hörn inom vilka varannan hörn ligger intill. Ett minsta klickskydd är ett klickskydd som använder så få klick som möjligt. Det minsta k för vilket ett klicktäcke existerar kallas klicktäckningsnumret för den givna grafen.

Förhållande till färgläggning

Ett klicktäcke av en graf G kan ses som en graffärgning av komplementgrafen för G , grafen på samma vertexuppsättning som har kanter mellan icke-angränsande hörn av G . Liksom klickomslag är graffärger partitioner av uppsättningen av hörn, men i delmängder utan angränsningar ( oberoende uppsättningar) snarare än klicker. En delmängd av hörn är en klick i G om och endast om den är en oberoende mängd i komplementet till G , så en partition av hörnen till G är ett klicktäcke av G om och endast om det är en färgning av komplementet till G .

Beräkningskomplexitet

Klicktäckningsproblemet i beräkningskomplexitetsteori är det algoritmiska problemet att hitta ett minimum för klicktäckning, eller (omformulerat som ett beslutsproblem ) att hitta ett klicktäcke vars antal klick är under en given tröskel. Att hitta en minsta klicktäckning är NP-svårt , och dess beslutsversion är NP-komplett . Det var ett av Richard Karps ursprungliga 21 problem som visades NP-kompletta i hans papper från 1972 "Reducibility Among Combinatorial Problems".

Ekvivalensen mellan klicktäckning och färgning är en minskning som kan användas för att bevisa NP-fullständigheten av klicktäckningsproblemet från den kända NP-fullständigheten av graffärgning.

I speciella klasser av grafer

Perfekta grafer definieras som de grafer där, för varje inducerad subgraf , det kromatiska antalet (minsta antal färger i en färgning) är lika med storleken på den maximala klicken . Enligt den svaga perfekta grafsatsen är komplementet till en perfekt graf också perfekt. Därför är de perfekta graferna också de grafer där, för varje inducerad subgraf, klickens omslagsnummer är lika med storleken på den maximala oberoende uppsättningen . Det är möjligt att beräkna klickens omslagsnummer i perfekta grafer i polynomtid .

En annan klass av grafer där den minsta klicktäckningen kan hittas i polynomtid är de triangelfria graferna . I dessa grafer består varje klickomslag av en matchning (en uppsättning osammanhängande par av intilliggande hörn) tillsammans med singleton-uppsättningar för de återstående omatchade hörnen. Antalet klick är lika med antalet hörn minus antalet matchade par. Därför, i triangelfria grafer, kan den lägsta klicktäckningen hittas genom att använda en algoritm för maximal matchning .

Den optimala uppdelningen i klick kan också hittas i polynomtid för grafer med begränsad klickbredd . Dessa inkluderar, bland andra grafer, kografer och avståndsärftliga grafer , som båda också är klasser av perfekta grafer.

Klickomslagsproblemet förblir NP-komplett på vissa andra specialklasser av grafer, inklusive kubiska plana grafer och enhetsskivor .

Approximation

Samma hårdhet av approximationsresultat som är kända för graffärgning gäller också för klicktäckning. Såvida inte P = NP , kan det därför inte finnas någon polynomisk tidsapproximationsalgoritm för någon ε > 0 som, på n -vertexgrafer, uppnår ett approximationsförhållande bättre än n ^{1 − ε} .

I grafer där varje vertex har högst tre grannar , förblir klicktäcket NP-hårt, och det finns en konstant ρ > 1 så att det är NP-svårt att approximera med approximationsförhållandet ρ eller bättre. Ändå är det i polynomtid möjligt att hitta en approximation med förhållandet 5/4. Det vill säga, denna approximationsalgoritm hittar ett klickskydd vars antal klick inte är mer än 5/4 gånger det optimala.

Bakers teknik kan användas för att tillhandahålla ett polynom-tidsapproximationsschema för problemet på plana grafer.

Relaterade problem

Det relaterade klickkanttäckningsproblemet gäller uppdelning av kanterna på en graf, snarare än hörnen, i subgrafer inducerade av klicker. Den är också NP-komplett.