Lösen der Exact2Is

Question

Ich habe das folgende Problem aufgetreten:

exact2is= {g hat genau 2 unabhängige Sets}

Angenommen, das angegebene Grafik G i kann ein unabhängiges Set finden, wie ich überprüfen kann, ob g genau 2 unabhängige Sätze hat.

(Ich kann prüfen, ob ein Diagramm unabhängig in O (1) enthält und auch ein unabhängiges Set in O (1) findet)

Ich dachte an, ein unabhängiges Set zu finden (falls vorhanden) von Größe K (falls vorhanden) k und dann einen Scheitelpunkt aus dem Set entfernen und prüfen, ob der Diagramm immer noch unabhängiger Satz von Größe K hat -Ner ich überprüfe, ob ich den Scheitelpunkt genau in die Grafik zurückscheide, genau wie es war.

Das Problem, das meine Idee nur prüfen kann, wenn ein Diagramm G mindestens 2 unabhängige Sets enthält und nicht genau.

Jeder hat eine Idee, wie ich überprüfen kann, ob ein Diagramm genau 2 unabhängige Sätze (in der Polynomialzeit hat) aufweist, die die Finde und Überprüfung des unabhängigen Satzes von O (1))?

Alle Hinweise oder Ideen werden geschätzt :) Danke

Answer 1

Zunächst einmal, wenn Sie feststellen können, ob ein Diagramm $ g $ einen unabhängigen Satz von Größe $ K $ enthält , dann können Sie auch ein solches Set effizient suchen. Dies ist als "Suchen-zu-Entscheidungs-Reduktion" bekannt. Hier ist die Grundidee. Wählen Sie einen beliebigen Scheitelpunkt $ V $ und entfernen Sie ihn. Wenn der Diagramm immer noch einen unabhängigen Satz von Größe $ K $ hat, dann gehen Sie weiter. Andernfalls enthalten alle unabhängigen Sätze der Größe $ K $ $ V $ . Entsprechend entfernen Sie $ V $ und alle seine Nachbarn und finden Sie einen unabhängigen Satz von Größe $ k-1 $ in der verbleibenden Grafik. Auf diese Weise können Sie einen unabhängigen Satz von Größe $ K $ wiederherstellen.

Sekunden, wie Sie prüfen, ob ein Diagramm zumindest zwei unabhängige Sätze der Größe $ K $ enthält, unternehmen Sie $ k \ geq 2 $ . Erstens bestimmen Sie, ob in mindestens einen enthält. Angenommen, es tut, sagen, $ i $ . Wenn $ J $ jedes andere unabhängige Set ist, dann $ i \ setminus J $ und $ j \ setminus i $ sind beide nicht leer (seit $ | i |= | j | $ ). Wenn insbesondere $ X \ in i \ setminus j $ und $ y $ ist jeder andere Scheitelpunkt in $ I $ , dann auch nach dem Hinzufügen der Kante $ (x, y) $ , der Set $ J $ stellt ein unabhängiges Set dar.

Dies führt zum folgenden Algorithmus: Für jedes Paar von Scheitelpunkten $ x, y \ in i $ prüfen Sie, ob $ G + (x, y) $ enthält einen unabhängigen Satz von Größe $ K $ . Wenn ja, unterscheidet sich dieses unabhängige Set notwendigerweise von $ I $ . Umgekehrt, wenn ein unabhängiger Satz von Größe $ K $ anders als $ I $ existiert, ist es notwendigerweise Seien Sie ein unabhängiges Set in $ g + (x, y) $ für einige $ x, y \ in i $ .

Drittens, wie Sie prüfen, ob ein Diagramm genau zwei unabhängige Sätze von Größe $ K $ enthält. Dies ist derselbe wie beim Überprüfen, ob ein Diagramm mindestens drei unabhängige Sätze enthält. Ich denke, dass es an diesem Punkt besser ist, wenn Sie versuchen, das obige Argument von zwei bis drei unabhängigen Sets zu verallgemeinern. Sie könnten stecken bleiben, aber Sie wissen es nicht, bis Sie es versuchen.

Answer 2

Wenn Sie finden dürfen ein von Größe $ K $ in $ \ \Mathcal o (1) $ , was Sie dann geschrieben haben, ist fast die Lösung.Nur zweimal finden Sie eine Größe von Größe $ K $ , und nach dieser Überprüfung, ob noch ein anderer ist.

In der Regel dürfen Sie jedoch für Oracle-Maschinen ein (in diesem Beispiel) nicht finden (in diesem Beispiel) ist innerhalb von $ \ Mathcal O (1) $ Zeit und Siedürfen nur prüfen, ob man existiert innerhalb $ \ mathcal o (1) $ .

Ich hoffe das hilft!