IB102 – úkol 11, příklad 1 Odevzdání: 21. 12. 2015
Vypracoval(a): UČO:
Skupina:
1. [2 body] Dokažte, že problém rozhodnout, zda v daném neorientovaném grafu existují
alespoň 2 různé k-kliky (dva úplné podgrafy s k vrcholy lišící se alespoň jedním vrcholem),
je NP-těžký. Jinak řečeno, dokažte, že jazyk 2-CLIQUE definovaný níže zadává NP-těžký
problém.
2-CLIQUE = { G, k | G je neorientovaný graf obsahující alespoň 2 různé k-kliky}
V důkazu můžete využít faktu, že problém kliky (definovaný níže) je NP-úplný:
CLIQUE = { G, k | G je neorientovaný graf obsahující k-kliku}.
Bonus [1 bod] Dokažte, že problém 2-CLIQUE je dokonce NP-úplný. Tedy dokažte
navíc, že 2-CLIQUE ∈ NP.
Bonus [1 bod] Dokažte, že jazyk n-CLIQUE definovaný níže je NP-úplný pro libovolné
n ≥ 1:
n-CLIQUE = { G, k | G je neorientovaný graf obsahující alespoň n různých k-klik}.