Problemă de acoperire a fisurilor
În teoria complexității de calcul , găsirea unei acoperiri minime a fisurilor este o problemă completă a NP a teoriei graficelor . Probalma a fost una dintre cele 21 de numere originale ale lui Richard Karp care au fost demonstrate NP-complete în eseul său din 1972 reducibilitatea între problemele combinatorii (reducibilitatea printre problemele combinatorii).
Problema de acoperire a fisurilor (uneori numită și partiție de fisură ) este problema de a determina dacă vârfurile unui grafic pot fi împărțite în k fisuri . Având în vedere o partiție a vârfurilor în k seturi, se poate verifica în timp polinomial că fiecare set formează o fisură, deci problema este în NP . Completitatea NP a acoperirii fisurilor se realizează prin reducerea colorabilității k a graficului . Pentru a vedea acest lucru, transformați mai întâi o instanță G a colorabilității k a graficului în graficul său complement G ' . O partiție a lui G ' în k fisuri corespunde apoi găsirii unei partiții a vârfurilor lui G în kseturi independente ; fiecăruia dintre aceste seturi li se poate atribui apoi o culoare pentru a crea o culoare k .
Problema de acoperire a marginii fisurilor aferente are în vedere seturile de fisuri care includ toate muchiile unui grafic dat. De asemenea, este complet NP.
Bibliografie
- Richard Karp , Reducibility Among Combinatorial Problems ( PDF ), în RE Miller și JW Thatcher (eds), Proceedings of a Symposium on the Complexity of Computer Computations , Plenum Press, 1972, 85-103. Adus 29/08/2008 .
- Michael R. Garey și David S. Johnson , Computers and Intractability: A Guide to Theory of NP-Completeness , WH Freeman, 1979, ISBN 0-7167-1045-5 . A1.2: GT19, p. 194.
