Halb Clique - NP vollständiges Problem

Question

Lassen Sie mich zunächst anfangen Dies ist ein Problem mit Hausaufgaben. Bitte geben Sie nur Ratschläge und verwandte Beobachtungen, bitte keine direkten Antworten. Nachdem dies gesagt ist, hier ist das Problem, das ich anschaue:

Lass halbclique = {$ Langle g rangle $ | $ G $ ist ein ungerichtes Diagramm mit einem vollständigen Untergraphen mit mindestens $ N/2 $ Knoten, wobei N die Anzahl der Knoten in $ g $} ist. Zeigen Sie, dass der halbe Klise NP-Complete ist.

Außerdem kenne ich Folgendes:

• In Bezug auf dieses Problem a Clique, ist definiert als ein ungerichteter Untergraphen des Eingangsdiagramms, wobei alle beiden Knoten durch eine Kante verbunden sind. EIN $ k $ -Clique ist eine Clique, die $ k $ Knoten enthält.
• Laut unserem Lehrbuch ist Michael Sipsers "Einführung in die Berechnungstheorie", S. 268, dass das Problem clique = {$ Langle G, K rangle $ | $ g $ ein ungerichteter Diagramm mit einem $ k $ -Clique} ist in NP ist
• Darüber hinaus ist nach der gleichen Quelle (auf PG 283) fest, dass sich Clique in NP-Complpete befindet (somit auch offensichtlich in NP).

Ich glaube, ich habe hier den Kernel einer Antwort, aber ich könnte verwenden Ein Hinweis darauf, was daran falsch ist oder verwandte Punkte, die für eine Antwort relevant sein könnten. Dies ist die allgemeine Idee, die ich bisher habe,

OK, ich würde zuerst bemerken, dass ein Zertifikat einfach eine halbe Qlique von $ text {size} Geq n/2 $ sein würde. Jetzt scheint es, dass ich tun müsste, einen Verifier zu erstellen, der eine Polynomzeitreduktion von Clique (von dem wir wissen, dass es NP-Complete ist) zu einem halben Clique darstellt. Meine Idee wäre, dass dies durch das Erstellen einer Turing-Maschine geschehen würde, die den Turing Machine-Verifizierer im Buch für Clique mit der zusätzlichen Einschränkung für den halben Clique ausführt.

Das klingt für mich richtig, aber ich vertraue mich selbst in diesem Thema noch nicht wirklich. Ich möchte noch einmal alle daran erinnern Dies ist ein Hausaufgabenproblem Bitte versuchen Sie, die Frage zu vermeiden. Jede Anleitung, die dies nicht zu tun ist, wäre sehr willkommen!

Answer 1

Nach Ihrer Beschreibung und Kommentaren zu urteilen, können Sie durch eine genaue Beschreibung des Besten geholfen werden, wie Reduzierungen verwendet werden können, um die NP-Vervollständigung nachzuweisen:

Ein Problem ist NP-Complete iff It in NP und es ist NP-Hard. Dies bedeutet, dass jeder Beweis für die NP-Vervollständigung zwei Teile hat: ein Beweis dafür, dass das Problem in NP liegt und ein Beweis dafür, dass es NP-HART ist.

Für den ersten Teil müssen Sie zeigen, dass Ja-Instanzen in der Polynomzeit mit einem geeigneten Zertifikat überprüft werden können. Alternativ können Sie zeigen, dass das Problem in der Polynomzeit durch eine nicht deterministische Turing-Maschine gelöst werden kann, dies wird jedoch normalerweise nicht so gemacht, wie Fehler leicht gemacht werden.

In Ihrem Fall hängt dies darum, dass Sie für jedes Diagramm mit einem $ N/2 $ -Clique einen Beweis finden, dass es tatsächlich eine solche Clique gibt, so dass Sie mit einem solchen Beweis ein Polynom einchecken können Zeit, dass es tatsächlich eine solche Clique gibt.

Für den zweiten Teil müssen Sie zeigen, dass das Problem NP-Hard ist. Dies geschieht in fast allen Fällen, indem beweist, dass Ihr Problem mindestens so schwierig ist wie ein anderes NP-harte Problem. Wenn der halbe Klise so schwer wie Clique ist, muss es auch NP-Hard sein.

Sie tun dies, indem Sie eine Reduzierung beweisen AUS CLIQUE, ZU Halbklique. Sie "reduzieren" das Problem und machen es "einfacher". Sie sagen: "Clique zu lösen ist schwer, aber ich habe bewiesen, dass Sie nur einen halben Klise lösen müssen, um Clique zu lösen." (Viele Menschen, sogar Experten, sagen gelegentlich das falsch herum :))

Es gibt verschiedene Arten von Reduktionen: Die am häufigsten verwendete Reduktion ist die, bei der Sie in diesem Fall Clique in Fälle von halb-cliques zuordnen, deren Größe in Polynomzeit höchstens polynomisch größer ist. Dies bedeutet, dass wir Clique auch durch Verkettung des Algorithmus und der Reduktion lösen können, wenn wir einen halben Clique lösen können.

Mit anderen Worten, wir müssen zeigen, dass wir Clique lösen können, wenn wir einen halben Clique lösen können. Wir tun dies, indem wir zeigen, dass wir für jede Instanz für Clique eine Instanz des halben Clique so entwerfen können, dass die Instanz von Clique eine "Ja"-Instanz ist, wenn die Instanz des halben Clique eine "Ja"-Instanz ist.

Der Beweis beginnt daher wie folgt: Angesichts eines Diagramms $ g = (v, e) $ kann ich ein Diagramm $ h = (v ', e') $ erstellen, so dass $ g $ einen $ k $ -Clique iff $ enthält H $ enthält eine $ n/2 $ -Clique. Ich überlasse diesen Teil Ihnen (dies ist der Teil, der Kreativität erfordert, dem Teil, in dem es um das spezifische Problem geht).

Answer 2

Sie scheinen ein wenig verloren zu sein. Sie möchten zeigen, dass ein halb-Clique $ ge $ clique, was bedeutet, dass Sie nach einem Poly-Zeit-Algorithmus suchen, der Clique-Instanzen als Eingang nimmt und halb-Clique-Instanzen mit der Eigenschaft "Ja" eingibt. Ja "ES und" Nein "Eingänge sind zu" Nein "s.

Grundsätzlich ist es die Aufgabe, ein Diagramm $ G $ und eine Nummer $ k $ zu nehmen und ein neues Diagramm $ H $ (und keine Nummer) auszugeben G $ hat eine Clique mit Größe $ k $.

Der folgende Spoiler enthält einen Hinweis darauf, wie diese Reduzierung durchführt:

Versuchen Sie, $ H $ zu verdienen, indem Sie (in irgendeiner Weise) eine angemessene Clique auf $ g $ (in irgendeiner Weise) anfügen, plus eine Reihe von Scheitelpunkten, die mit nichts verbunden sind.

Answer 3

Sie können vom Scheitelpunktabdeckungsproblem reduzieren. Wenn der Komplementgraphen des angegebenen Graphen einen Scheitelpunktabdeckung weniger als N/2 -Knoten aufweist, hat dieses Diagramm eine Clique von mehr als N/2 -Knoten, die eine halbe Clique sein wird. Geben Sie nur an, dass es schwierig ist, das Problem der Scheitelpunktabdeckung zu lösen.