LP Entspannung von unabhängigen Set

13

Ich habe die folgende LP Relaxation von Maximum Independent Set ausprobiert

maxichxich

st xich+xj1 (ich,j)E
xich0

Ich erhalte 1/2 für jede Variable für jeden Kubik nicht-bipartiten Graphen ich versuchte.

  1. Gilt das für alle verbundenen kubischen nicht bipartiten Graphen?
  2. 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.

Jaroslaw Bulatow
quelle
Die Lösung ist sicherlich nicht einzigartig. In einem kubischen zweigliedrigen Graphen können Sie eine optimale Lösung mit x i = 1 in einem Teil und x i = 0 in dem anderen Teil haben. xi=1/2xi=1xi=0
Jukka Suomela
1
Entschuldigung, ich habe einen wichtigen Teil verpasst, ich betrachte nur nicht-zweigeteilte kubische Graphen. Jeder zweigliedrige kubische Graph, den ich ausprobierte, hatte eine integrale Lösung
Jaroslaw Bulatow,
Sie müssen auch "verbunden" hinzufügen, wenn Sie nicht eindeutige Lösungen vermeiden möchten.
Jukka Suomela
2
(1) Sie haben vergessen, die Nicht-Negativitätsbeschränkungen zu schreiben. (2) Für zweiteilige Graphen entspricht der optimale Wert dieser LP-Relaxation immer der maximalen Größe einer unabhängigen Menge. Dies ist eine unmittelbare Folge des Satzes von König .
Tsuyoshi Ito
2
@Yaroslav: Eine Nebenfrage: Wie zeichnet man diese Grafiken?
StackExchange for All

Antworten:

16

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 j1 summieren , haben Sie i 3 x i3 n / 2 , und daher ist das Optimum höchstens n / 23n/2xi+xj1i3xi3n/2n/2 .

Die Lösung für alle ixi=1/2i ist trivialerweise durchführbar und somit auch optimal.

In einem zweigliedrigen kubischen Graphen hat jeder Teil die Hälfte der Knoten und die Lösung xi=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/2xi+xj=1{i,j}xi=1/2

Jukka Suomela
quelle
2
Wie ich in einem Kommentar zu der Frage schrieb, brauchen Sie nur die Zweiteiligkeit, um die Existenz einer integralen optimalen Lösung zu beweisen (dies erfordert jedoch einen anderen Beweis als Ihren).
Tsuyoshi Ito
@ Tsuyoshi: Ja, König's Theorem ist gut zu bedenken. Zusammen mit der obigen Beobachtung wird beispielsweise gezeigt, dass jeder zweigliedrige kubische Graph eine 1-Faktorisierung aufweist (dh, er kann in drei perfekte Übereinstimmungen unterteilt werden). Natürlich ist dies der "falsche" Weg, um dieses Ergebnis zu beweisen, aber ich denke, dass er die Kraft von König's Theorem gut demonstriert - wenn Sie sich nur an König's Theorem erinnern, gibt es viele klassische Ergebnisse in der Graphentheorie, die Sie dann leicht neu erfinden können .
Jukka Suomela
12

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

Mohit Singh
quelle
Richtig, siehe auch Satz 5.6 dieses Papier für einen sehr einfachen Algorithmus, der effizient findet eine halbzahlig Lösung.
Jukka Suomela
LP mit Clique-Einschränkungen löste etwa 50% mehr Grafiken aus dem obigen Satz. Wo finde ich die SDP-Formulierung?
Yaroslav Bulatov
6

K4

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 zu Kk. 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

Nathann Cohen
quelle
1
Eines der Probleme bei diesem Ansatz ist, dass wenn Sie einen nicht bipartiten kubisch dreieckfreien Graphen haben (und es gibt viele davon ...), die Formulierung genau der in der Frage entspricht und wir genau die gleiche haben schlechte Nachrichten. Generell denke ich, dass wir immer Graphen konstruieren können, in denen sich alle Knoten in a befindenk-clique und es gibt keine (k+1)-clique und zeige das xich=1/k für alle ich ist die einzigartige optimale Lösung der LP.
Jukka Suomela
Interessanterweise hängt dies mit der Einfachheit von IndependentSet in Akkorddiagrammen zusammen
Yaroslav Bulatov
Ich habe einige Experimente durchgeführt, und die Lösung dieser LP-Relaxation war immer ein wesentlicher Bestandteil von Akkorddiagrammen
Yaroslav Bulatov,
1
@YaroslavBulatov Es gibt einen Grund für Ihre Beobachtung. Die Clique-Ungleichungen und Nicht-Negativitätsgrenzen ergeben die konvexe Hülle unabhängiger Mengen, wenn und nur wenn der Graph perfekt ist. Akkorddiagramme sind perfekt.
Austin Buchanan