Max-Cut-Algorithmus, der nicht funktionieren sollte, unklar, warum

OK, das mag wie eine Hausaufgabe erscheinen und in gewissem Sinne ist es das auch. Als Hausaufgabe in einem Bachelor-Algorithmuskurs gab ich den folgenden Klassiker:

Geben Sie bei einem ungerichteten Graphen $G=(V,E)$ einen Algorithmus an, der einen solchen Schnitt $(S,\bar{S})$ , dass $\delta(S,\bar{S})\geq |E|/2$ , wobei $\delta(S,\bar{S})$ die Anzahl der Kanten ist, die den Schnitt kreuzen. Die Zeitkomplexität muss $O(V+E)$ .

Aus irgendeinem Grund habe ich viele der folgenden Lösungen erhalten. Jetzt nimmt es zu viel Zeit in Anspruch, es ist also keine Frage der Benotung, aber ich wurde neugierig. Es "scheint" nicht korrekt zu sein, aber alle meine Versuche, Gegenbeispiele anzufertigen, sind fehlgeschlagen. Hier ist es:

1. Setze $S\leftarrow \emptyset$
2. Sei $v$ ein Scheitelpunkt von maximalem Grad in der Grafik
3. Füge $v$ zu $S$
4. Löschen Sie alle Kanten neben $v$
5. Wenn $\delta(S,\bar{S}) < |E|/2$ kehre zu 2 zurück

Beachten Sie, dass sich $E$ in Schritt 5 auf das ursprüngliche Diagramm bezieht. Beachten Sie auch, dass wir Schritt 4 übersprungen hätten, dies wäre offensichtlich falsch (zum Beispiel die Vereinigung eines Dreiecks mit zwei isolierten Kanten).

Nun hat jeder einfache Beweis das folgende Problem - es kann sein, dass wir beim Hinzufügen eines neuen Scheitelpunkts $v$ tatsächlich entfernen S $|S|$Kanten aus dem Schnitt, während $d(v)$ neue Kanten hinzugefügt werden (wobei $d(v)$ sich auf das Diagramm mit gelöschten Kanten bezieht). Die Sache ist, dass, wenn dies für unsere Sache schädlich ist, dies bedeutet, dass dieser Scheitelpunkt $v$ einen immer höheren Grad "hatte", so dass er früher "hätte ausgewählt" werden müssen.

Ist das ein bekannter Algorithmus? Gibt es ein einfaches Gegenbeispiel dafür?

^{Mein früherer Anspruch vom haben berücksichtigt nicht den Schnitt der Größen2/4bereits in dem Graphen. Die folgende Konstruktion scheint zu einemO(1) zu führen (ich habe eine Frage unter math.stackexchange.com für einen strengen Beweis erstellt)$\frac{2}{c+6}$$n^2/4$Fraktion.$O\left(\frac{1}{\log c}\right)$}

Der Algorithmus funktioniert bei Vereinigungen mehrerer getrennter vollständiger Graphen unterschiedlicher Größe schlecht. Wir bezeichnen den vollständigen Graphen auf Eckpunkten als K n . Betrachten Sie das Verhalten des Algorithmus auf K n : Er fügt wiederholt einen beliebigen Scheitelpunkt hinzu, der noch nicht in S zu S enthalten ist - alle diese Scheitelpunkte sind identisch, und daher spielt die Reihenfolge keine Rolle. Einstellen der Anzahl der Eckpunkte, die vom Algorithmus noch nicht zu S hinzugefügt wurden | ˉ S | = k ist die Größe des Schnitts in diesem Moment k ( n - k ) .$n$$K_n$$K_n$$S$$S$$S$$|\bar{S}| = k$$k (n-k)$

Überlegen Sie, was passiert, wenn der Algorithmus in mehreren getrennten Diagrammen mit x i -Konstanten zwischen 0 und 1 ausgeführt wird. Wenn k i die Anzahl der Elemente ist, die im i- ten vollständigen Diagramm noch nicht in S enthalten sind , wird der Algorithmus wiederholt addiert ein Scheitelpunkt zu S aus dem vollständigen Graphen mit dem höchsten k i , wobei die Bindungen willkürlich unterbrochen werden. Dies führt zu rundenbasierten Additionen von Eckpunkten zu S : Der Algorithmus addiert einen Eckpunkt aus allen vollständigen Graphen mit dem höchsten k = k i und dann aus allen vollständigen Graphen mit $K_{x_i n}$$x_i$$k_i$$S$$i$$S$$k_i$$S$$k = k_i$ (wobei k i nach der vorherigen Runde aktualisiert wurde) und so weiter. Sobald ein kompletter Graph einen Vertex zu S in einer Rundehinzugefügt hat, wird dies von da an für jede Runde getan.$k_i=k-1$$k_i$$S$

Sei die Anzahl der vollständigen Graphen. Sei 0 < x i ≤ 1 mit 0 ≤ i ≤ c - 1 der Größenmodifikator für den i- ten vollständigen Graphen. Wir ordnen diese Größenmodifikatoren von groß nach klein und setzen x 0 = 1 . Wir haben jetzt , dass , wenn es c ' Graphen mit genau k Elementen noch nicht hinzugefügt S , dann ist die Größe des Schnittes zu diesem Zeitpunkt ist Σ c ' - 1 i = 0 k $c$$0 < x_i \leq 1$$0 \leq i \leq c - 1$$i$$x_0 = 1$$c'$$k$$S$ . Die Gesamtzahl der Kanten beträgt | E | = ∑ c - 1 i = 0 x i n ( x i n - 1 $\sum_{i=0}^{c'-1} k (x_i n - k) = k n \sum_{i=0}^{c'-1} (x_i) - c' k^2$ .$|E| = \sum_{i=0}^{c-1} \frac{x_i n (x_i n - 1)}{2} \approx \frac{n^2}{2} \sum_{i=0}^{c-1} x_i^2$

Es ist zu beachten, dass eine quadratische Funktion in k ist und daher ein Maximum hat. Wir werden daher mehrere lokal maximale Schnitte haben. Wenn zum Beispiel c = 1 ist, liegt unser maximaler Schnitt bei k = $k n \sum_{i=0}^{c'-1} x_i - c' k^2$$k$$c=1$ der Größen$k=\frac{n}{2}$ . Wir gehen holenx1so dassx1=1/2-ε, der das zweite vollständige Graphen bedeutetwird nicht die Größe von lokal maximal Schnitt an verändernk=$\frac{n^2}{4}$$x_1$$x_1 = 1/2 - \varepsilon$ . Wir erhalten dann einen neuen lokal maximal Schnitt beik=3/8n-ε'und so holen wirx2=3/8n-ε"(mitε,ε',ε"kleinen Konstanten). Wir werden das ignorierenεs für den Moment und einfach davon ausgehenkönnen wir wählenx1=1/2- wir sollten sicherstellenx1n=$k=\frac{n}{2}$$k=3/8 n - \varepsilon'$$x_2 = 3/8 n - \varepsilon''$$\varepsilon, \varepsilon', \varepsilon''$$\varepsilon$$x_1 = 1/2$, dies hat jedoch keine Auswirkung auf das Endergebnis, wennngroß genug ist.$x_1 n = \frac{n}{2} - 1$$n$

Wir möchten die lokalen Maxima unserer Schnitte finden. Wir differenzieren zu k , was n ∑ c ' - 1 i = 0 ( x i ) - 2 c ' k ergibt . Gleich 0 ergibt k = $k n \sum_{i=0}^{c'-1} (x_i) - c' k^2$$k$$n \sum_{i=0}^{c'-1} (x_i) - 2 c' k$$0$, was einen Schnitt der Größen2ergibt$k = \frac{n}{2c'} \sum_{i=0}^{c'-1} x_i$.$\frac{n^2}{4c'} \left(\sum_{i=0}^{c'-1} x_i\right)^2$

Sei das im vorhergehenden Absatz bestimmte k , wenn c ' = i ist . Wir werden sicherstellen, dass die Formel gilt, indem wir verlangen, dass x i n < k i - alle vollständigen Graphen i ' mit i ' > i kleiner sind als k i dieses lokal maximalen Schnitts und daher die Größe des Schnitts nicht erhöhen. Dies bedeutet, dass wir an diesen k i c Schnitte haben , die größer sind als alle anderen Schnitte, die vom Algorithmus gefunden werden.$k_i$$k$$c'=i$$x_i n < k_i$$i'$$i'>i$$k_i$$c$$k_i$

Wenn wir , erhalten wir die Wiederholung x i = $x_i n < k_i$(plus einige kleineε) mitx0=1. Wenn man dies löst, erhält manxi= ( 2 $x_i = \frac{1}{2c'} \sum_{i=0}^{c'-1} x_i$$\varepsilon$$x_0 = 1$ :Siehe meine Frage auf math.stackexchange.comfür die Ableitung von @Daniel Fisher. Einstecken inn$x_i = \frac{\binom{2i}{i}}{4^i}$und unter Verwendung unserer Einsicht in die Wiederholung erhalten wir Schnitte der Größen$\frac{n^2}{4c'} \left(\sum_{i=0}^{c'-1} x_i\right)^2$$\frac{n^2}{4c'} \left(2c' \frac{\binom{2c'}{c'}}{4^{c'}}\right)^2 = n^2 c' \left(\frac{\binom{2c'}{c'}}{4^{c'}}\right)^2$. Using properties of this central binomial coefficient, we have $\lim_{c' \to \infty} c' \left(\frac{\binom{2c'}{c'}}{4^{c'}}\right)^2 = \frac{1}{\pi}$ (also see my question on math.stackexchange.com).

The number of edges is approximately $\frac{n^2}{2} \sum_{i=0}^{c-1} x_i^2 = \frac{n^2}{2} \sum_{i=0}^{c-1} \left(\frac{\binom{2i}{i}}{4^i}\right)^2$. By known properties we have $\frac{1}{\sqrt{4i}} \leq \frac{\binom{2i}{i}}{4^i}$. Filing in gives at least $\frac{n^2}{2} \sum_{i=0}^{c-1} \left(\frac{1}{\sqrt{4i}}\right)^2 = \frac{n^2}{8} \sum_{i=0}^{c-1} \frac{1}{i}$ which is asymptotically $\frac{n^2}{8} \log c$ as $c$ goes to infinity.

We therefore have $\frac{\delta(S, \bar{S})}{|E|}$ is asymptotically equal to $\frac{8}{\pi \log c}$ as $c$ goes to infinity, showing that the algorithm can return cuts that are arbitrarily low fractions of $|E|$.

After a while of thinking and asking around, here's a counter-example, courtesy of Ami Paz:

Let $n$ be even and $G$ be a graph which is the union of $K_n$ with a matching of $n+2$ vertices (that is, a matching with $n/2+1$ edges).

How does the algorithm run on this graph? It just takes vertices from the clique part in arbitrary order. After having taken $k$ vertices from the clique, the cut is of size $k\cdot (n-k)$. This is maximal for $k=n/2$, which gives a cut of size $\frac{n^2}{4}$, while the number of edges in the graph is $\frac{n^2}{2}+1$.

The algorithm as prescribed will continue adding vertices from the clique, reducing the number of edges crossing the cut, until what remains from the clique is just a single edge. At this point it cannot obtain anything better than $\frac{n}{2}+2$.