Il problema della cricca contro il set indipendente

Question

Supponiamo di avere un grafico non indirizzato $ G = (v, e) $, noto sia ad Alice che a Bob, Alice ottiene una serie indipendente di $ G $. Bob ottiene una cricca $ B ⊆ v $.

C'è qualche algoritmo in $ O ( log^2 n) $ pezzi che trova se$ A ∩ b = Ø $?

Questo è un noto problema di complessità della comunicazione chiamato problema di cis descritto da Yannakakis.

• Note di lettura; L'affermazione è Teorema 3
• Link al libro di testo di Nisan & Kushilevitz

Non sono sicuro del perché e come funziona esattamente. e quale parte del $ n/2 $ I vertici sono ridotti da entrambi i giocatori.

PS Sono giunto alla conclusione che un indipendente e una cricca possono intersecarsi al massimo un vertice.