Riduzione da cricca-6 a cricca-3

Question

Ricordiamo che $ g $ ha una cricca di dimensioni $ k $ se ha un sottocrista completo composto da $ k $ vertici.

Definiamo il problema $ clique-k $ come segue: $$ { langle g rangle mid g text {è un grafico non diretto che contiene una clique di dimensioni} k } $$

---

Domanda: Trova una riduzione $ f $ da $ clique-6 $ a $ cLique-3 $ in modo tale che l'input di $ f $ sia un grafico $ g $ con $ n $ vertici, $ f (g) $ è un grafico con $ o (n^2) $ vertici e $$ g in cricca-6 leftrighrow f (g) in clique-3 $$

La complessità temporale richiesta per il calcolo di $ f $ è $ o (n^4) $.

Non sono sicuro di come affrontare questo problema e sarei grato se qualcuno possa fornire informazioni direzioni alla soluzione.