Beweis, dass der spärlichste Schnitt NP-hart ist

9

Überall, wo ich über das dünnste Schnittproblem lese, heißt es nur, dass das Problem als NP- hart bekannt ist. Wo finde ich einen Beweis dafür? Welches bekannte NP- harte Problem reduziert sich auf das dünnste Schnittproblem?

Ich konnte keinen Beweis in Vaziranis Buch "Approximationsalgorithmen" finden, in dem der Leighton Rao-Algorithmus vorgestellt wird, oder in dem Buch "Computer und Intraktabilität", in dem viele NP- vollständige Probleme zusammengefasst sind. Ich konnte es nicht finden, indem ich (mit offensichtlichen Suchzeichenfolgen) bei Google suchte. Es gibt ein Papier von Chawla et al., Das Khots UGC-Vermutung annimmt und die Härte der Annäherung an den spärlichsten Schnitt beweist. Ich hatte gehofft, einen Beweis zu sehen, der keine Vermutung voraussetzt.

Der Beweis sollte nur ein bekanntes NP- hartes Problem auf den spärlichsten Schnitt reduzieren.

Vielen Dank,

Arpita Korwar.

cc.complexity-theory reference-request np-hardness Arpita Korwar
quelle
5
Das Papier "Sparsest Schnitte und Engpässe in Grafiken" von David W. Matula, Farhad Shahrokhi, reduziert das Max-Cut-Problem. Maximaler Härtenachweis findet sich bei Garey Johnson. sciencedirect.com/science/article/pii/0166218X9090133W
Jagadish
2
@ Jagadish Antwort?
Tyson Williams

Antworten:

10

[Vom Kommentar verschoben]

Das Papier " Sparsest Schnitte und Engpässe in Grafiken " von David W. Matula, Farhad Shahrokhi, reduziert das Max-Cut-Problem. Max-Cuts Härtebeweis findet sich bei Garey Johnson.

Jagadisch
quelle
Danke für den Hinweis. Ich möchte erwähnen, dass dies die einheitliche Version des spärlichsten Schnitts ist (im Grunde genommen eine Erweiterung des Diagramms). Vor einigen Jahren fiel es mir schwer, einen richtigen Schiedsrichter zu finden, der einen Beweis enthielt. Musste es von Max Cut ausarbeiten.
Chandra Chekuri