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

21

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,S¯) , dass δ(S,S¯)|E|/2 , wobei δ(S,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
  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 δ(S,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?

Yonatan
quelle
2
Es sieht ähnlich aus wie die 2-Approximation für die Scheitelpunktabdeckung. Ich denke, der richtige Greedy-Algorithmus würde den Scheitelpunkt mit mehr Nachbarn im anderen Teil auswählen und verschieben, bis es keinen solchen Scheitelpunkt mehr gibt, und es ist nicht schwierig zu zeigen, dass an diesem Punkt die Antwort mindestens . Die Richtigkeit dieses Algorithmus hängt jedoch von der folgenden Tatsache ab: Wir betrachten den Unterschied zwischen der Anzahl der Nachbarn für den Scheitelpunkt auf den beiden Seiten des Schnitts und nicht nur dem Maximalgrad. Auch der richtige Algorithmus bewegt sich Knoten in beiden Richtungen, nicht nur von ˉ S bis S . |E|/2S¯S
Kaveh
3
@Kaveh Ich denke, OP kennt den von Ihnen beschriebenen Algorithmus (er hat ihn als Hausaufgabe zugewiesen). Seine Frage ist, ob der von ihm beschriebene Algorithmus eine Annäherung erreicht.
Sasho Nikolov
2
@ MohammadAl-Turkistany siehe Nikolovs Kommentar.
vb le
1
Beachten Sie auch, dass die 16/17-Approximation NP-hart ist, nicht 1/2. GW geben ~ 0.878 Näherung mit SDP in ihrer wegweisenden Arbeit.
Yonatan
1
@Yonatan Siehe diese Frage cstheory.stackexchange.com/questions/3846/…
Mohammad Al-Turkistany

Antworten:

13

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)2c+6n2/4Fraktion.O(1logc)

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 ) .nKnKnSSS|S¯|=kk(nk)

Ü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 kKxinxikiSiSkiSk=ki (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.ki=k1kiS

Sei die Anzahl der vollständigen Graphen. Sei 0 < x i1 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 (c0<xi10ic1ix0=1ckS . Die Gesamtzahl der Kanten beträgt | E | = c - 1 i = 0 x i n ( x i n - 1 )i=0c1k(xink)=kni=0c1(xi)ck2 .|E|=i=0c1xin(xin1)2n22i=0c1xi2

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 = nkni=0c1xick2kc=1 der Größen2k=n2 . Wir gehen holenx1so dassx1=1/2-ε, der das zweite vollständige Graphen bedeutetwird nicht die Größe von lokal maximal Schnitt an verändernk=nn24x1x1=1/2ε . 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=nk=n2k=3/8nεx2=3/8nεε,ε,εεx1=1/2, dies hat jedoch keine Auswirkung auf das Endergebnis, wennngroß genug ist.x1n=n21n

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 = nkni=0c1(xi)ck2kni=0c1(xi)2ck0, was einen Schnitt der Größen2ergibtk=n2ci=0c1xi.n24c(i=0c1xi)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.kikc=ixin<kiii>ikicki

Wenn wir , erhalten wir die Wiederholung x i = 1xin<ki(plus einige kleineε) mitx0=1. Wenn man dies löst, erhält manxi= ( 2 ixi=12ci=0c1xiεx0=1 :Siehe meine Frage auf math.stackexchange.comfür die Ableitung von @Daniel Fisher. Einstecken inn2xi=(2ii)4iund unter Verwendung unserer Einsicht in die Wiederholung erhalten wir Schnitte der Größen2n24c(i=0c1xi)2n24c(2c(2cc)4c)2=n2c((2cc)4c)2. Using properties of this central binomial coefficient, we have limcc((2cc)4c)2=1π (also see my question on math.stackexchange.com).

The number of edges is approximately n22i=0c1xi2=n22i=0c1((2ii)4i)2. By known properties we have 14i(2ii)4i. Filing in gives at least n22i=0c1(14i)2=n28i=0c11i which is asymptotically n28logc as c goes to infinity.

We therefore have δ(S,S¯)|E| is asymptotically equal to 8πlogc as c goes to infinity, showing that the algorithm can return cuts that are arbitrarily low fractions of |E|.

Alex ten Brink
quelle
3
With a slight modification, your construction gives 1/4. Fix ε and chose a sufficiently large N. Let V={1,,N}. Connect every two vertices in {1,,εN} with an edge; then additionally connect every two vertices in V w.p. ε2. The total number of edges is approximately (εn)2/2+ε2(n2/2)=ε2n2. The algorithm finds a cut that cuts approximately ε2n2/4 edges (up to lower order terms in ε).
Yury
I think I'll rewrite my answer to just include the final results (with more detail) soon, as it's a bit of a mess right now.
Alex ten Brink
1
Regarding the sum n22i=0c1((2ii)4i)2, since each term is Θ(1/(i+1)), the sum is a harmonic series which sums to Θ(logc), and in total we get Θ(n2logc).
Yuval Filmus
12

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 Kn 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(nk). This is maximal for k=n/2, which gives a cut of size n24, while the number of edges in the graph is n22+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 n2+2.

Yonatan
quelle
1
Nice counterexample.
Kaveh
this still gets very close to |E|/2 though. it would be nice to see an example where the algorithm does worse
Sasho Nikolov