SDP-Relaxation des unabhängigen Sets

Ich schaue auf Seite 28 von Lovasz "Semidefinite Programme und kombinatorische Optimierung" und es gibt die folgende Annäherung an die Unabhängigkeitszahl des Graphen

max u^{'} Z u

$\max u' Z u$

Z ≻ 0

$Z\succ 0$

Z_{i j} = 0 \forall i j \in E (G)

$Z_{ij}=0 \ \forall ij\in E(G)$

t r (Z) = 1

$tr(Z)=1$

Kann ich ein unabhängiges Set (oder etwas in der Nähe eines unabhängigen Sets) direkt aus der Lösung der SDP-Relaxation erhalten? Laut Lovasz ist SDP der einzige bekannte Weg, um dieses Problem genau für perfekte Grafiken zu lösen. Stimmt das noch?

Klarstellung: Es gibt eine ähnliche SDP-Relaxation für die Größe des maximalen Schnitts, und ich kann die vollständige Lösung (den tatsächlichen Schnitt anstelle seiner Größe) erhalten, indem ich die Quadratwurzel von Z nehme und eine zufällige Rundung durchführe (Kapitel 6 des Williamson / Shmoys-Buches) ). Ich frage mich, ob es für dieses Problem eine ähnliche Technik gibt

ds.algorithms graph-theory semidefinite-programming independent-set Jaroslaw Bulatow
quelle

Bei der ersten Frage verstehe ich nicht wirklich, was Sie unter "der tatsächlichen unabhängigen Menge" verstehen. Das SDP ist eine Entspannung, und so begrenzt der optimale Wert des SDP die Unabhängigkeitszahl von oben. Wenn sie sich unterscheiden, erreicht kein unabhängiger Satz den optimalen Wert des SDP. Dies kann der Fall sein, wenn das Diagramm nicht perfekt ist. Könnten Sie klarer machen, was Sie für Ihre "tatsächliche unabhängige Menge" benötigen?

Yoshio Okamoto

Ich möchte den größten unabhängigen Satz erhalten und nicht die "Größe des größten unabhängigen Satzes"

Jaroslaw Bulatow

Vielen Dank für die Klarstellung, aber ich frage mich immer noch. Das SDP für den maximalen Schnitt wird zur Annäherung verwendet. Die zufällige Rundung ergibt nämlich einen Schnitt, dessen Wert "nahe" am optimalen Schnittwert liegt, nicht unbedingt einen echten Maximalschnitt. Wenn Sie eine ähnliche Technik benötigen, ist das, was Sie wirklich wollen, wahrscheinlich ein unabhängiger Satz, dessen Größe nahe an der Unabhängigkeitszahl liegt. Oder konzentrieren Sie sich auf perfekte Grafiken oder möchten sich mit allgemeinen Grafiken befassen?

Yoshio Okamoto

Ich möchte Maximum Independent Set in Perfect Graph finden. ipsofacto gibt eine Lösung, aber es erfordert die Lösung mehrerer SDPs

Yaroslav Bulatov

Antworten:

Ich glaube, SDP ist die einzige bekannte Technik, um das Problem der maximalen unabhängigen Menge auf perfekten Graphen zu lösen. Um das unabhängige Set zu erhalten, könnte man Folgendes tun. Erraten Sie, ob sich ein Scheitelpunkt in der unabhängigen Menge befindet, löschen Sie ihn und lösen Sie das SDP. Wenn derselbe Wert zurückgegeben wird, gibt es eine unabhängige Menge ohne diesen Scheitelpunkt. Machen Sie diesen Scheitelpunkt also neben allen anderen Scheitelpunkten und fahren Sie fort. Dies sollte Ihnen einen tatsächlichen unabhängigen Satz geben.

Andernfalls haben wir einen Scheitelpunkt der unabhängigen Menge identifiziert, und wir können ihn entfernen und mit dem verbleibenden Diagramm fortfahren.

ipsofacto
quelle

Darüber hinaus wurde dies implementiert und funktioniert recht gut (mit einigen Optimierungen): E. Alper Yıldırım und Xiaofei Fan-Orzechowski über das Extrahieren maximal stabiler Mengen in perfekten Graphen unter Verwendung der Theta-Funktion von Lovász , Computational Optimization and Applications 33 , 229–247, 2006 . dx.doi.org/10.1007/s10589-005-3060-5

András Salamon

Interessant ... es scheint, dass keine Perfektion erforderlich ist, damit die SDP-Schätzung der Unabhängigkeitszahl genau ist (hier ein Beispiel: mathoverflow.net/questions/57336/… ), daher sollte dies für eine größere Klasse von Graphen funktionieren

Yaroslav Bulatov

@ Jaroslaw: Du hast recht, Perfektion ist nicht erforderlich. Wenn Sie jedoch die von ipsofacto vorgeschlagene Strategie anpassen, muss das Löschen von Scheitelpunkten ebenfalls dieselbe Eigenschaft haben. Diese Bedingung wird automatisch erfüllt, wenn das Diagramm perfekt ist. Andernfalls müssen Sie vorsichtig sein.

Yoshio Okamoto

Ich bin mir nicht sicher, ob Lovasz 'Kommentar noch gilt. In jüngster Zeit wurden einige Arbeiten zu diesem (und verwandten) Problemen an perfekten Graphen durchgeführt. Unter dem folgenden Link finden Sie Techniken, bei denen Nachrichten weitergeleitet werden, anstatt SDPs zu lösen: http://www.cs.columbia.edu/~jebara/papers/uai09perfect.pdf

Nicholas Ruozzi
quelle

Interessantes Papier, verstehe ich es richtig, dass, wenn das Max-Produkt in einem perfekten Diagramm konvergiert, die gierige Dekodierung die maximale unabhängige Menge wiederherstellt?

Jaroslaw Bulatow

Ich habe das Papier überflogen, aber ich konnte nicht herausfinden, wie die Methoden das maximale unabhängige Mengenproblem für perfekte Graphen in Polynomzeit lösen. Die Anzahl der maximalen Cliquen kann in einem perfekten Graphen exponentiell sein, sodass die Laufzeiten in Korollarien 1 und 2 nicht polynomisch sind. Obwohl ich den Inhalt von Abschnitt 7 nicht sehr gut verstehe, sehe ich nicht, welches lineare Optimierungsproblem die Methode in Abschnitt 7 löst. Die Experimente werden für das Problem der maximalen Übereinstimmung durchgeführt, jedoch nicht für das Problem der maximalen unabhängigen Menge.

Yoshio Okamoto

@yoshio Du bist richtig. Die LP für MWIS ist bekanntermaßen ein integraler Bestandteil, wenn Sie die entsprechenden Einschränkungen für alle (exponentiell vielen) Cliquen berücksichtigen. Und es ist die Perfektion des Cliquengraphen, die in dem Artikel diskutiert wird. Es sieht so aus, als würden die Autoren nur vermuten, dass das Max-Produkt auf einem NMRF immer die richtige MAP-Zuordnung erzeugt.

Nicholas Ruozzi

Vielen Dank. Kann ich dann annehmen, dass das Papier keinen Polynom-Zeit-Algorithmus für das maximale unabhängige Mengenproblem für perfekte Graphen enthält?

Yoshio Okamoto

@ YoshioOkamoto: es scheint so. Ein kürzlich veröffentlichtes Papier gibt ein Beispiel für ein perfektes Diagramm, bei dem dieser Ansatz zu einer falschen Lösung konvergiert. Abbildung 3 von "Überprüfung der MAP-Schätzung, Weitergabe von Nachrichten und perfekte Diagramme " ( datalab.uci.edu/papers/AISTATS_perfect_graphs.pdf )

Yaroslav Bulatov