Ich habe die folgende LP Relaxation von Maximum Independent Set ausprobiert
Ich erhalte für jede Variable für jeden Kubik nicht-bipartiten Graphen ich versuchte.
- Gilt das für alle verbundenen kubischen nicht bipartiten Graphen?
- Gibt es eine LP-Entspannung, die für solche Grafiken besser funktioniert?
Update 03/05 :
Hier ist das Ergebnis der auf Cliquen basierenden LP-Entspannung, die Nathan vorgeschlagen hat
Ich habe die Experimente hier zusammengefasst. Interessanterweise scheint es einige nicht-bipartite Graphen zu geben, für die die einfachste LP-Relaxation von wesentlicher Bedeutung ist.
graph-theory
co.combinatorics
linear-programming
Jaroslaw Bulatow
quelle
quelle
Antworten:
Nicht-bipartite verbunden kubische Graphen haben die einzigartige optimale Lösung ; in einem zweigliedrigen kubischen Graphen haben Sie eine integrale optimale Lösung.xi=1/2
Beweis: Wenn Sie in einem kubischen Graphen über alle Nebenbedingungen x i + x j ≤ 1 summieren , haben Sie ∑ i 3 x i ≤ 3 n / 2 , und daher ist das Optimum höchstens n / 23n/2 xi+xj≤1 ∑i3xi≤3n/2 n/2 .
Die Lösung für alle ixi=1/2 i ist trivialerweise durchführbar und somit auch optimal.
In einem zweigliedrigen kubischen Graphen hat jeder Teil die Hälfte der Knoten und die Lösungxi=1 in einem Teil ist daher auch optimal.
Jede optimale Lösung muss eng sein, das heißt, wir müssen und daher x i + x j = 1 für jede Kante { i , j } haben . Wenn Sie also eine ungerade Zyklus haben, müssen Sie wählen x i = 1 / 2 für jeden Knoten im Zyklus. Und wenn der Graph verbunden ist, wird diese Auswahl überall verbreitet.∑i3xi=3n/2 xi+xj=1 {i,j} xi=1/2
quelle
Diese LP ist für alle Graphen halbintegral, dh es gibt eine optimale Lösung für jede Variable in {0,1 / 2,1}. Es folgt einfach aus einem Satz von Nemhauser und Trotter. Natürlich folgt für die LP des Komplementproblems (Vertex Cover) die gleiche Schlussfolgerung der Halbintegralität. Wenn der Graph zweiteilig ist, ist die Lösung ganzheitlich. Es folgt einfach aus dem Max-Flow-Min-Cut-Theorem oder dem Arbeiten mit Extrempunktlösungen dieser LP. Auch die 1/2 Kanten bilden einen ungeraden Zyklus.
Natürlich ist diese LP nicht gut für die Lösung von IS-Problemen. Das Hinzufügen von Clique-Einschränkungen oder SDPs ist ein viel besserer Ansatz.
Vertexpackungen: Struktureigenschaften und Algorithmen GL Nemhauser und Trotter-Math. Program., 1975
quelle
In der Doktorarbeit von Sergiy Butenko aus dem Jahr 2003 wurden einige andere LP-Relaxationen von MIS sowie einige quadratische Relaxationen behandelt.
quelle
Dies wird als fraktionale unabhängige Satznummer bezeichnet. Sie finden dort einige Informationen: http://en.wikipedia.org/wiki/Fractional_coloring oder im Buch "Fractional Graph Theory" von Daniel Ullman und Edward Scheinerman ( http://www.ams.jhu.edu/~ers / fgt / ).
Praktisch ist diese Formulierung NP-schwer zu berechnen, obwohl alle Variablen stetig sind -> die Anzahl der Cliquen ist exponentiell und schwer zu berechnen .... Sie können jedoch nur einige spezielle Cliquen aufzählen, zum Beispiel nur die Kanten (die Sie gerade gemacht haben) oder Kanten + Dreiecke oder alle Cliquen bis zuKk . Immerhin kann der Wert nur "repräsentativer" für den realen Integerwert (*) werden :-)
Nathann
(*) Vor diesem Hintergrund haben Sie theoretisch einen willkürlich großen Unterschied zwischen dem optimalen Ergebnis in der LP, in der alle Cliquen vertreten sind, und der optimalen unabhängigen Menge
quelle