Risolvere Exact2is usando è

Question

Ho riscontrato il seguente problema:

exact2is= {g ha esattamente 2 set indipendenti}

Supponendo che un grafico G posso trovare un set indipendente come posso controllare se G ha esattamente 2 set indipendenti.

(Posso controllare se un grafico contiene set indipendente in O (1) e trovare anche alcuni set indipendenti in O (1))

Stavo pensando di trovare un set indipendente (se ce ne è) di taglia k e quindi rimuovere un vertice dal set e controllare se il grafico ha ancora un set indipendente di dimensioni k -fter controllo ritornando il vertice sul grafico esattamente come lo era.

Il problema La mia idea Controlla solo se un grafico G contiene almeno 2 set indipendenti e non esattamente.

Qualcuno ha un'idea come posso controllare se un grafico ha esattamente 2 set indipendenti (in tempo polinomiale e dato il fatto che trovare e controllare se c'è un set indipendente è o (1))?

Qualsiasi indizio o idee sarà apprezzato :) Grazie

Answer 1

Prima di tutto, se è possibile determinare se un grafico $ G $ contiene un set indipendente di dimensioni $ k $ , quindi puoi anche trovare un set così in modo efficiente. Questo è noto come "riduzione della ricerca-decisione". Ecco l'idea di base. Scegli un vertice arbitrario $ V $ e rimuoverlo. Se il grafico ha ancora un set indipendente di dimensioni $ k $ , quindi continuare ad andare. Altrimenti, tutti i set indipendenti di dimensioni $ k $ contiene $ V $ . Di conseguenza, rimuovere $ V $ e tutti i suoi vicini e trova un insieme indipendente di dimensioni $ k-1 $ nel grafico rimanente. In questo modo, puoi recuperare un set indipendente di dimensioni $ k $ .

Secondo, come verificare se un grafico contiene almeno due set indipendenti di dimensioni $ k $ , supponendo $ k \ geq 2 $ . Innanzitutto, determina se in contiene almeno uno. Supponiamo che lo faccia, dire $ i $ . Se $ J $ è qualsiasi altro set indipendente, quindi $ i \ setminus j $ e $ J \ Setmino I $ sono entrambi non vuoti (dal momento che $ | i |= | j | $ ). In particolare, se $ x \ in i \ setminus j $ e $ y $ è qualsiasi altro vertice in $ i $ , quindi anche dopo aver aggiunto il bordo $ (x, y) $ , il set $ J $ costituirà un set indipendente.

Questo porta al seguente algoritmo: per ogni coppia di vertici $ x, y \ in $ , controlla se $ G + (x, y) $ contiene un set indipendente di dimensioni $ k $ . In tal caso, questo set indipendente è necessariamente diverso da $ i $ . Viceversa, se un set indipendente di dimensioni $ k $ diverso da $ I $ esiste, quindi sarà necessariamente essere un set indipendente in $ G + (x, y) $ per alcuni $ x, y \ in $ .

In terzo luogo, come verificare se un grafico contiene esattamente due set indipendenti di dimensioni $ k $ . Questo è lo stesso che controlla se un grafico contiene almeno tre set indipendenti. Penso che a questo punto, è meglio se si tenta di generalizzare l'argomento di cui sopra da due a tre serie indipendenti. Potresti rimanere bloccato, ma non saprai finché non ci provi.

Answer 2

Se ti è consentito Trova A è di dimensioni $ k $ in $ \Mathcal O (1) $ , quindi quello che hai scritto è quasi la soluzione.Solo due volte trovi un è di dimensioni $ k $ , e dopo questo controllo per vedere se c'è ancora un altro.

Ma di solito, per macchine Oracle, non è consentito trovare un (in questo esempio) è all'interno di $ \ Mathcal O (1) $ Tempo e tuSono consentiti solo a Controllare se si esiste entro $ \ mathcal o (1) $ .

Spero che questo aiuti!