Problem med klicktäckning

Klicktäckningsproblemet  är ett beräkningsproblem som består i att bestämma möjligheten att dela upp hörn av en graf i klicker . Är NP-komplett ; ingår i listan över 21 NP-kompletta Karp-problem [1] .

Givet en uppdelning av hörn i mängder är det möjligt att bestämma i polynomtid att varje mängd bildar en klick så att problemet tillhör NP -klassen . NP-fullständigheten av klicktäckningsproblemet följer av dess reduktion till graffärgningsproblemet : att sönderdela grafen per klick motsvarar att hitta sönderdelningen av komplementpunkten i oberoende uppsättningar (en färg kan tilldelas var och en av dessa uppsättningar, vilket ger a -färgning).

Den minsta klicktäckningsstorleken för ett diagram är det minsta antal som det finns ett klicktäcke för.

Det relaterade problemet med att hitta korsningsnumret tar hänsyn till uppsättningar av klickar som inkluderar alla kanter på en given graf; detta problem är också NP-komplett.

Anteckningar

  1. ↑ Karp, 1975 , sid. 16-38.

Litteratur