Vertex isoperimetrische Zahl eines Graphen

Vertex isoperimetrische Zahl eines Graphen - NP-hart?

Die isoperimetrische Scheitelpunktzahl eines Graphen ist . Mehrere wissenschaftliche Arbeiten geben an, dass das Problem der Berechnung der isoperimetrischen Scheitelpunktzahl eines Graphen NP-hart ist, ohne Beweis oder Referenz. $G=(V,E)$
$i_V(G) = \min\{\frac{|N(S)|}{|S|} : S \subseteq V, 1\le |S|\le \frac{|V|}{2}\}$

Können Sie eine Referenz angeben, bei der das folgende Problem NP-vollständig dargestellt ist: Bei einem Graphen $G$ und einer Zahl $t$ besteht die Frage darin, ob $G$ höchstens isoperimetrische Scheitelpunktzahl hat $t$ ?

reference-request graph-theory np-hardness Serge Gaspers
quelle

Ist das nicht nahe am Maximalschnitt?

Saeed

Max Cut liegt tatsächlich näher an der Cheeger-Konstante, wobei in der obigen Definition

| N (S) |

$|N(S)|$ wird durch die Anzahl der Kanten mit einem Endpunkt in

S

$S$ und dem anderen in

N (S)

$N(S)$ . Für die Cheeger-Konstante sind NP-Härtebeweise in der Literatur leicht zu finden.

Serge Gaspers

Folgendes kann hilfreich sein. sciencedirect.com/science/article/pii/0020019081900508

Chandra Chekuri

Antworten:

Das folgende Papier: Zu einem isoperimetrischen Problem für Hamming-Graphen LH Harper. enthält Folgendes:

Das vertex-isoperimetrische Problem ist im Allgemeinen NP-vollständig [8], so dass keine polynomiell begrenzte Lösung bekannt ist und es unwahrscheinlich ist, dass eine existiert.

Wo Referenz [8] MR Garey, DS Johnson, Computer und Intraktabilität ist: Ein Leitfaden zur Theorie der NP-Vollständigkeit ,

Dieses Buch enthält normalerweise entweder einen Beweis oder einen Verweis auf den Beweis. Leider habe ich momentan keinen Zugang zu dem Buch.

user53923
quelle

Die NP-harte Problemvariante in Harpers Artikel ist jedoch anders: Wenn ein Graph G und eine ganze Zahl k gegeben sind, finden Sie eine Teilmenge S der Eckpunkte mit | S | = k, die | N (S) | minimiert.

Gamow

Ich verstehe, du hast recht.

user53923