Ist die Cheeger-Konstante -hard?

Ich habe in unzähligen Artikeln gelesen, dass die Bestimmung der Cheeger-Konstante eines Graphen -hard ist. Es scheint ein Volkstheorem zu sein, aber ich habe weder ein Zitat noch einen Beweis für diese Aussage gefunden. Wem soll ich das zuschreiben? In einer alten Arbeit (Isoperimetric Numbers of Graphs, J. Comb. Theory B, 1989) beweist Mohar diese Behauptung nur "für Graphen mit mehreren Kanten". $\mathsf{NP}$

reference-request graph-theory spectral-graph-theory Delio M.
quelle

Antworten:

Auch ich bin auf dieses Problem gestoßen, als ich ein Papier schrieb, für das eine Angabe zur Härte der (oder Cheeger-Konstante) erforderlich war, die als. Das klassische Papier von Leighton und Rao über Separatoren ( http://dl.acm.org/citation.cfm?id=331526 ) erwähnt, dass dies ein schwieriges Problem ist, und verweist auf das Papier von Garey, Johnson und Stockmeyer ( http: / /www.sciencedirect.com/science/article/pii/0304397576900591 $\min_{S \subset V, |S| \leq |V|/2} |\delta(S)|/|S|$ ). Ich konnte für eine Weile nicht herausfinden, worauf sie sich bezogen, da es keine Erwähnung der Kantenerweiterung in dem genannten Papier gibt. Ich habe mit Avi Wigderson darüber gesprochen. Es stellte sich schließlich heraus, dass man die Härte von Max-Cut verwenden kann, wie in dem Artikel von Garey et al. Gezeigt, um relativ leicht zu zeigen, dass die Kantenexpansion hart ist. Ich vergesse die Details jetzt, aber es sollte nicht schwer sein, sie neu zu erstellen. Das Papier von Blum et al. Über die Härte der Prüfung, ob ein Graph ein Superkonzentrator ist, impliziert nicht direkt die Härte der Kantenexpansion. Sie sind technisch nicht das gleiche Problem.

Chandra Chekuri
quelle

Mein Papier, das die Kantenexpansionshärte verwendet, ist das folgende: onlinelibrary.wiley.com/doi/10.1002/net.20165/abstract . Wir verweisen auf das Leighton-Rao-Papier und das von Garey, Johnson, Stockmeyer bezüglich der Härte der Kantenexpansion.

Chandra Chekuri

Vielen Dank! Technisch gesehen ist die Härte der Bestimmung der Cheeger-Konstante in der Literatur also nicht bewiesen?

Delio M.

@DelioM. Die Kaibel-Referenz in einer von Mohammeds Antworten hat einen vollständigen Beweis. Es ist nur die Garey-Johnson-Stockmeyer-Reduktion vom ungewichteten maximalen Schnitt zur minimalen Halbierung, mit einem kurzen Beweis, dass in den durch die Reduktion erzeugten Grafiken der dünnste Schnitt eine Halbierung ist.

Sasho Nikolov

Obwohl ich gestehen muss, dass ich verloren bin. Ich dachte immer, dass Max-Cut mit der Frage zusammenhängt, wie zweigeteilt ein Graph ist. Wie kann dies helfen, um festzustellen, wie verbunden ein Diagramm ist? Wie kann der zweitniedrigste Eigenwert des vorzeichenlosen Laplace-Operators an den zweitniedrigsten Eigenwert des Laplace-Operators gebunden werden? Dass eine Untergrenze offensichtlich ist, aber eine Obergrenze?

Delio M.

@DelioM. Max Cut wird zunächst auf Min Bisection reduziert, indem weitere Scheitelpunkte hinzugefügt und das Komplement des resultierenden Graphen verwendet werden. Diese Reduktion bezieht sich also darauf, wie nahe ein Diagramm an einem anderen Diagramm liegt (bezogen auf das Komplement des ersten Diagramms).

n

$n$

Sasho Nikolov

Der tatsächliche Beweis für die Härte der Berechnung der Cheeger-Konstante (oder Kantenexpansion) wurde von Kaibel in einem technischen Bericht durch eine Reduktion des MAX-Cut-Problems gegeben (siehe Satz 2). Der Beweis ist eine Erweiterung des Beweises der Härte des Equicut-Problems, den Garey, Johnson und Stockmeyer in einigen vereinfachten NP-vollständigen Graphproblemen gegeben haben . $NP$ $NP$

V. Kaibel: Zur Erweiterung von Graphen von 0/1-Polytopen. Technischer Bericht arXiv: math.CO/0112146, 2001

BEARBEITEN : Das folgende Argument ist falsch , wie von Chekuri hervorgehoben, und zu Bildungszwecken hinterlassen.

Dies ist keine von Ihnen angeforderte Referenz, sondern erklärt den Folklorestatus des Härteergebnisses.

Hier ist eine Beweisidee für die CoNP-Vollständigkeit der Entscheidung, ob ein zusammenhängender kubischer Graph ein Kantenexpander ist, und daher ist die Bestimmung der Cheeger-Konstante CoNP-hart. $h(G)$

Das minimale Bisektionsproblem ist vollständig $NP$ für verbundene kubische Graphen. Hier wollen wir entscheiden, ob ein Graph mit einer ganzen Zahl in zwei gleich große Teile aufgeteilt werden kann, so dass die Anzahl der Schnittkanten kleiner als . $G$ $k$ $k$

Es ist zu beachten, dass die Ergänzung dieses Problems der Entscheidung entspricht, ob der Graph ein Expander ist oder nicht (jede ausgeglichene Partition von hat Schnittkanten von mehr als ). $G$ $V$ $k$

PS Arora in diesem Seminar erklärt, dass es - , ein Expander-Diagramm ( zu erkennen . http://www.cs.princeton.edu/~zdvir/apx11slides/arora-slides.pptx $CoNP$ $\alpha$

Mohammad Al-Turkistany
quelle

Dieser Beweis funktioniert auch nicht, da die Größe der Min-Halbierung nichts über die Kantenerweiterung selbst aussagt. Beispielsweise kann ein nicht verbundener Graph auf Eckpunkten eine minimale Halbierung .

2 n

$2n$

(n - 2)^{2}

$(n-2)^2$

Sasho Nikolov

Der Graph ist ein kubischer Graph, und für diese Klasse ist das Minimalhalbierungsproblem NP-vollständig.

G

$G$

Mohammad Al-Turkistany,

@SashoNikolov Ich habe noch nie jemanden gesehen, der sich für die Erweiterung nicht verbundener Grafiken interessiert.

Mohammad Al-Turkistany

Arora, nicht Aurora. Ich bezweifle nicht, dass es schwierig ist , sich für entscheiden. In zwei Antworten haben Sie jedoch weder einen Hinweis mit Beweis noch einen Beweis gegeben. Die nicht verbundenen Grafiken sollen Ihnen nur zeigen, dass Ihre Argumente falsch sind. Dein "Fix" funktioniert auch nicht. Ich kann Ihnen leicht einen zusammenhängenden kubischen Graphen mit einer großen minimalen Halbierung und einer beliebig nahe Null liegenden Cheeger-Konstante zeigen. Die beiden Probleme hängen zusammen, aber nicht auf die triviale Weise, die Sie vorschlagen.

h (G) \geq α

$h(G) \geq \alpha$

Sasho Nikolov

@ MohammadAl-Turkistany: Nehmen Sie zwei verbundene brückenlose kubische Graphen, die Expander sind, einen mit 2n Scheitelpunkten und den anderen mit n Scheitelpunkten, und verbinden Sie sie mit drei Kanten, indem Sie auf jeder Seite drei neue Scheitelpunkte hinzufügen, indem Sie drei Kanten unterteilen. Jetzt wird die minimale Halbierung groß ( ), weil Sie einen guten Teil des größeren Expanders abschneiden müssen, aber die Erweiterung ist klein, weil Sie die beiden Expander aufteilen können, indem Sie nur drei Kanten abschneiden.

Ω (n)

$\Omega(n)$

Chandra Chekuri