Klicka problem

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 27 november 2019; kontroller kräver 4 redigeringar .

Klickproblemet tillhör klassen av NP-kompletta problem inom grafteorin . Den formulerades första gången 1972 av Richard Karp . [ett]

En klick i en oriktad graf är en delmängd av hörn, var och en av vilka två är förbundna med en kant på grafen. Det är med andra ord en komplett subgraf av den ursprungliga grafen. Klickstorleken definieras som antalet hörn i den. Klickproblemet finns i två versioner: i igenkänningsproblemet krävs det att avgöra om det finns enklick med storleken k i en given graf G , medan det i en beräkningsvariant krävs att hitta enklick med maximal storlek i en given graf G.

NP-komplett

NP-fullständigheten för klickproblemet följer av NP-fullständigheten för det oberoende vertexuppsättningsproblemet. Det är lätt att visa att en nödvändig och tillräcklig förutsättning för existensen av en klick av storlek k är närvaron av en oberoende uppsättning av storlek åtminstone k i komplementet till grafen. Detta är uppenbart, eftersom en subgrafs fullständighet innebär att dess komplement inte innehåller några kanter.

Ett annat bevis på NP-fullständighet finns i Algoritmer: Konstruktion och analys. [2]

Algoritmer

När det gäller andra NP-kompletta problem har en effektiv algoritm för att hitta en klick av en given storlek ännu inte hittats. En uttömmande sökning av alla möjliga subgrafer av storlek k , som kontrollerar om minst en av dem är komplett, är ineffektiv, eftersom det totala antalet sådana subgrafer i en graf med v hörn är lika med binomialkoefficienten ${v \choose k} = \frac{v!}{k!(vk)!}.$

En annan algoritm fungerar så här: två klick av storleken n och m "limmas" till en stor klick med storleken n + m , och en separat vertex av grafen antas vara en klick av storleken 1 . Algoritmen avslutas så snart inga fler sammanslagningar kan göras. Körtiden för denna algoritm är linjär, men den är heuristisk , eftersom den inte alltid leder till att man hittar en klick med maximal storlek. Ett exempel på ett misslyckat slutförande är fallet när de hörn som hör till den maximala klicken är separerade och är i mindre klick, och de senare inte längre kan "limmas ihop" tillsammans.

Det är bevisat att, under villkoret av olikhet mellan klasserna P och NP , finns det ingen polynomapproximationsalgoritm med absolut fel lika med godtycklig . Betrakta en graf u - den direkta produkten av en graf och en klick av storlek . Uppenbarligen kommer grafens klicknummer att vara lika med . Antag att det finns en approximationsalgoritm med ett absolut fel lika med . Sedan matar vi grafen som indata och under villkoret får vi . Låta vara klickar av grafer av formen , där . Notera giltigheten av ojämlikheten och ersätt den med ovanstående ojämlikhet enligt följande: . Efter transformationen får vi , vilket betyder att det existerar sådant att och därför är klickproblemet lösbart i polynomtid, vilket motsäger olikhetsvillkoret för klasserna P och NP. $k\in {\mathbb {N}}$ $G$ ${\displaystyle G^{k}=G\ gånger C_{k))$ $G$ $C_{k}$ $k$ $G^{k}$ $\omega (G^{k})=\omega (G)\cdot k$ $A$ $k\in {\mathbb {N}}$ $A$ $G^{k+1}$ $OPT\leqslant A(I)+k$ $\omega (G^{k+1})-A(G^{k+1})=(k+1)\cdot \omega (G)-A(G^{k+1})\ leqslant k$ $C_{i}$ $G^{i}$ $1\leqslant i\leqslant k+1$ $C_{i}\leqslant \omega (G)$ $(k+1)\cdot \omega (G)-\sum _{i=1}^{k+1}|C_{i}|\leqslant k$ $\sum _{i=1}^{k+1}\omega (G)-|C_{i}|\leqslant k$ $i$ $C_{i}=\omega (G)$

Se även

Bron-Kerbosh-algoritm - snabbt hitta alla klick

Anteckningar

↑ Karp, Richard (1972). "Reducerbarhet bland kombinatoriska problem" (PDF) . Proceedings of a Symposium on the Complexity of Computer Computations . Plenum Press. Arkiverad från originalet (PDF) 2011-06-29 . Hämtad 2010-03-21 . Utfasad parameter används |deadlink=( hjälp )
↑ Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmer: konstruktion och analys = Introduktion till algoritmer / Ed. I. V. Krasikova. - 2:a uppl. - M. : Williams, 2005. - 1296 sid. — ISBN 5-8459-0857-4 .

Litteratur

Cook, Stephen A. (1971). "Komplexiteten i satsbevisande förfaranden" . Proceedings of the Third Annual ACM Symposium on Theory of Computing . Shaker Heights, Ohio. pp. 151–158. Arkiverad från originalet 2006-05-03 . Hämtad 2007-06-11 . Utfasad parameter används |deadlink=( hjälp ) Arkiverad 3 maj 2006 på Wayback Machine
Garey, Michael R. & Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , W. H. Freeman, ISBN 0-7167-1045-5 A1.2: GT19, sid.194.

Länkar

Utmanande riktmärken för maximal klick, maximalt oberoende set, minsta vertexskydd och vertexfärgning

NP-kompletta problem
Maximeringsproblem med stapling (packning)	Förpackning i behållare tvådimensionell packning linjär packning packning efter vikt förpackning efter värde Ryggsäcksproblemet
grafteori mängdteori	Vertex Cover Problem Klicka problem Problemet med en oberoende uppsättning (uppsättning) Ställtäckningsproblem Steiners problem Problemet med resande säljare Generaliserat resandeförsäljarproblem
Algoritmiska problem	Tillfredsställelseproblem för booleska formler (i konjunktiv normal form)
Logiska spel och pussel	Generaliserade taggar (spel i N 2 -1) kortaste lösningen problem Problem vars lösningar tillämpas i Tetris Generaliserat Sudoku problem Latinsk kvadrat fyllningsproblem Kakuros uppgift
Svårighetsklasser Operationsforskning Optimering Kombinatorisk optimering Tillämpad matematik Teori om algoritmer Dynamisk programmering 21 NP-komplett Karp-problem