Verifica se un $ k $ -subset di un grafico è una copertura vertice in tempo $ o (kn) $

Question

Dato un grafico $ G = (v, e) $ insieme a $ | V | = n, | e | = m $. Sto leggendo un $ tessit {Brute Force} $ Soluzione per determinare se ogni copertura del vertice candidato della dimensione $ k leq n $ è una copertura vertice. Il grafico non ha loop.

Come da pagina 2 delle note qui noi abbiamo:

• 1) $ C (n, k) = o (n^k) $ $ k $-Subset di $ V $
• 2) $ O (kn) $ È ora di verificare se un sottoinsieme è una copertura del vertice

Sto prendendo in considerazione 2).

Quello che vorrei pensare sarebbe prendere ogni vantaggio nel nostro grafico, per il quale c'è un massimo $ {n scegli 2} = o (n^2) $, e controlla il sottoinsieme candidato per vedere se almeno uno dei vertici è un endpoint del bordo, che prenderebbe $ O (kn^2) $ controlli.

Non sono sicuro di come sia arrivato l'autore $ O (kn) $ Operazioni, qualsiasi intuizione apprezzata.