Effizienter Algorithmus für MIN-Schnitt mit angegebener Anzahl von Scheitelpunkten

Question

Betrachten Sie ein Diagramm mit Scheitelpunkten $ V $ und Kanten $ E $ . Die Standardversion des MIN-Schnittproblems besteht darin, die Partition von $ V $ in eine (nicht leere) Teilmenge $ zu finden C $ und seine ergänzende $ \ bar {c} $ , um die Anzahl der Kanten zu minimieren, die zwischen $ C $ und $ \ bar {c} $ . Algorithmen sind für dieses Problem bekannt, das es bei der Polynomzeit lösen. Meine Frage ist, was, wenn man zusätzlich die Einschränkung angibt, die $ | C |= n $ für einige $ n <| v | $ ? Das heißt, wir möchten den Satz von $ n $ -Verpunkte mit der minimalen Anzahl von Kanten finden, die ihn an den Rest der Scheitelpunkte verbinden. Gibt es für diesen Fall auch effiziente Algorithmen? Ich bin sowohl in der Frage interessiert, ob dieses Problem in der Polynomzeit formal lösbar ist (was ich vermuten würde, dass es ist) und auch in den Algorithmen in der Praxis am besten sind.

Answer 1

für $ n=Frac {| V |} 2 $ , es heißt Minimum-Bissiection, und es ist np-hart. Es gibt einen $ o (\ log ^ {3/2} n) $ -Apprximation: " Eine polylogarithmische Annäherung der Mindestbisektion ".

Wenn Sie interessiert sind, ist das allgemeinere Problem in mehreren Komponenten derselben Größe, und es wird als ausgewogene Graph-Partitionierung bezeichnet. Für mehr als 2 Teile gibt es keine endliche Annäherung, es sei denn, P= NP: "Ausgewogene Grafik Partitionierung" (Andreev, Rakke) , da Sie nicht effizient überprüfen können, ob die Antwort 0 ist.

Wenn die Teile nicht unbedingt genau ausgewogen sind (ein kleines Ungleichgewicht ist zulässig ist), existiert ein $ O (\ \ log n) $ -Approximationsalgorithmus: "ausgewogene Partitionen von Bäumen und Anwendungen" .

---

Einige Algorithmen (auch überprüfen https://en.wikipedia.org/wiki/graph_partition "/a > und "Verweise" Abschnitte der folgenden Papiere):

.

• Lokale Suche mit verschiedenen Aromen: Wir beginnen mit einiger Partitionierung und versuchen dann, Scheitelpunkte zwischen den Teilen zu tauschen, um den Schnitt zu minimieren. Z.B. Wir berechnen "Gain" für jeden Scheitelpunkt (Verbesserung, wenn wir sie an einen anderen Teil bewegen) und Scheitelpunkte mit der maximalen Verstärkung tauschen. Sein Vorteil ist, dass Sie es nach einem anderen Algorithmus anwenden können.

• Spectral-Partitionierung (siehe zB Spectral Graph-Theorie und Grafik Partitionierung ): Verwendet den zweiten Eigenvektor einer laplazischen Matrix, um die Partitionierung anzunähern (z. B. durch Verschieben der kleinsten $ | v | / 2 $ -Oordinaten in der ersten Teil). Funktioniert überraschend gut. Ich bin jedoch nicht sicher, ob es an den Fall angepasst werden kann, wenn Sie eine unausgeglichene Bissiection (z. B. $ 1: 2 $ anstelle von $ 1: 1 $ ).

• lineare Einbettung: "Ausgeglichene Einteilung durch lineare Einbettung" . Wir bündelten die Scheitelpunkte in ein eindimensionales Array, während wir die Summe über alle Paare von Scheitelpunkten minimieren: Der Abstand zwischen ihnen multipliziert mit dem Gewicht ihres Randes. Dann teilen wir dieses Array gerade in aufeinanderfolgende Brocken der erforderlichen Größen auf. Funktionierte nicht so gut in meiner Erfahrung.

• (Anzeigen) Unsere Papier: "Multi-dimensionales ausgewogenes Diagramm Partitionierung via. Prognostizierter Gradientenabstieg ", wo wir Gradient-Abstieg verwendet haben, um eine Mindestbisektion zu finden: Für jeden Scheitelpunkt führen wir eine Variable ein, die grob eine Wahrscheinlichkeit darstellt, dass der Scheitelpunkt zum ersten Teil gehört, und die Minimierung des Schnittes verringert sich zur eingeschränkten Optimierung von a Quadratische Funktion. Es ist ein bisschen, in der Praxis durch eine fein abgestimmte lokale Suche zu übertreffen, aber es funktioniert wirklich gut, wenn Sie mehrere Balance-Einschränkungen haben.

Abgesehen von der spektralen Methode können alle, die alle an die Partitionierung des Graphen in beliebigen Proportionen anpassen können.

Es gibt auch Standard-Löser: kahip , metis . In meiner Erfahrung war Kahip ziemlich gut. Ich bin nicht sicher, ob sie jedoch auf Teile von willkürlichen Größen unterstützen.