9. feladatsor megoldása (vázlat) 1. Minden lehetséges ponthármas ellenőrzése cn^3 lépésszámú algoritmus. 2. Az NP-beliség triviális. Ha az algoritmust egy tetsz. G gráffal és k=n-1 paraméterekkel hívjuk, ahol |V(G)|=n, akkor a válasz pontosan akkor lesz igenlő, ha G-nek van n élből álló kör, vagyis Hamilton-köre, tehát a probléma NP-teljes. 3. Az összes lehetséges pontpárra a fokszámokat kell kiszámítani, így a kérdés cn^3 lépésben biztosan megválaszolható. 4. NP triv. Legyen G tetsz. gráf, melyre |V(G)|=n. Hívjuk meg n-szer a szóban forgó algorimust úgy, hogy minden alkalommal G egy-egy (mindig különböző) pontjához "ragasztjuk hozzá" a k pontú teljes gráfot oly módon, hogy egy közös pontjuk legyen. Ez pontosan akkor tér vissza n-szer nemmel, ha G-ben nincs k-as klikk, aminek megválaszolása NP-teljes, így ez a probléma is az. 5. A kapott G gráfra először ellenőrizzük, van-e benne n/2 ftlen pont. Ha van, akkor (sorba rendezzük a pontokat) az első pontot ideiglenesen összekötjük G minden pontjával. Ha a szubrutin erre a gráfra igennel tér vissza akkor G1-nek nevezzük a most megkonstruált gráfot, ha a válasz nem, akkor az n/2 független ponthoz az első pont szükséges volt, tehát megjelöljük, és G1:=G. Ezt tovább folytatva, a k-adik pontra (k-t minden mással összekötve) igen esetén Gk:={G(k-1) és a k-adik pont mindennel összekötve}, nem esetén Gk:=G(k-1), és a k-adik pontot megjelöljük. Mire Gn-t is legyártjuk, pont n/2 db független pont lesz jelölt, mert Gn-ben van n/2 db független pont és a nem jelöltek nem lehetnek a független ponthalmazban, mert Gn-en belül mindennel össze vannak kötve. n/2-nél több pontot sem kaphatunk, mert akkor az elsőnek megjelölt nem lett volna szükséges az n/2 ftlen ponthoz, ami ellentmondás. (Ha n páratlan, n/2 helyett n/2 fölső egészrésze értendő.) 6. NP trivi, ha az A részhalmaz egyetlen pontból áll, akkor a probléma éppen a közismerten NP-teljes háromszínezési problémával ekvivalens. 7. Elég minden pontnégyesre ellenőrizni, hogy az adott négy pont között van-e két-két ftlen, ill. hogy a maradék gráf 2-színezhető-e, vagyis páros, ami nyilván polinomidőben megtehető (pl. szélességi kereséssel). 8. NP trivi, legyen G tetsz gráf, és |V(G)|=n. Ekkor G(unió){4n db izolált pont} esetén az eredmény ekvivalens azzal, hogy G tartalmaz-e Hamilton-kört, vagyis NP-teljes. 9. Mivel G síkba rajzolható, nem tartalmazhat az ötpontú teljes gráffal izomorf részgráfot, ezért csak k<5 esetén nemtriviális a feladat. Ekkor viszont a kérdés cn^4 lépésben biztosan ellenőrizhető.