Approximationsalgorithmen für Maximum Independent Set in speziellen Klassen von Graphen

23

Wir wissen , dass Maximum Unabhängiges Set (MIS) ist schwer innerhalb eines Faktors von angenähert für jedes ε > 0 , es sei denn P = NP. Für welche speziellen Klassen von Graphen sind bessere Approximationsalgorithmen bekannt?n1ϵϵ>0

Für welche Graphen sind Polynom-Zeit-Algorithmen bekannt? Ich weiß, dass dies für perfekte Diagramme bekannt ist, aber gibt es noch andere interessante Klassen von Diagrammen?

Arindam Pal
quelle
1
Die genaue (nicht angenäherte) Version dieser Frage: cstheory.stackexchange.com/q/2503/109
András Salamon

Antworten:

19

Es gibt eine wirklich beeindruckende Liste aller bekannten Grafikklassen, die einige nicht-triviale Algorithmen für MIS enthalten: siehe diesen Eintrag auf der Website für Grafikklassen .

Suresh Venkat
quelle
8
Diese Liste zielt ausschließlich auf exakte Algorithmen ab. In der Näherung könnte die Hauptklasse das PTAS in planaren Graphen, Graphen begrenzter Gattungen und Graphen ohne h-Moll sein.
Yixin Cao
Danke Suresh. Die Liste ist ziemlich umfangreich. Danke auch an Yan für die Annäherungsergebnisse.
Arindam Pal
2
Die entsprechenden Referenzen sind: Brenda S. Baker: Approximationsalgorithmen für NP-vollständige Probleme auf planaren Graphen. J. ACM 41 (1): 153 & ndash; 180 (1994); David Eppstein: Durchmesser und Treewidth in Minor-Closed-Graph-Familien. Algorithmica 27 (3): 275 & ndash; 291 (2000); Erik D. Demaine, Mohammad Taghi Hajiaghayi, Ken-ichi Kawarabayashi: Algorithmische Graph-Minor-Theorie: Zerlegung, Approximation und Färbung. FOCS 2005: 637 & ndash; 646. Siehe auch: courses.csail.mit.edu/6.889/fall11/lectures/L08.html und courses.csail.mit.edu/6.889/fall11/lectures/L09.html
Christian Sommer
12

Ich habe keinen guten Überblick über dieses Problem, kann aber einige Beispiele nennen. Ein einfacher Näherungsalgorithmus besteht darin, eine bestimmte Reihenfolge der Knoten zu finden und die Knoten, die in der unabhängigen Menge enthalten sein sollen, gierig auszuwählen, wenn nicht einer ihrer vorherigen Nachbarn in der unabhängigen Menge ausgewählt wurde.

Wenn der Graph eine Entartung , ergibt die Verwendung der Entartungsreihenfolge eine d- Annäherung. daher für Graphen der Entartung n 1 - ϵddn1-ϵ haben wir eine ausreichend gute Näherung.

Es gibt ein paar andere Techniken für Annäherungen, die auch funktionieren, aber ich kenne sie nicht gut. Siehe: http://en.wikipedia.org/wiki/Baker%27s_technique und http://courses.engr.illinois.edu/cs598csc/sp2011/Lectures/lecture_7.pdf

Für die Polynomalgorithmen, die die Probleme genau lösen, ist der von Suresh angegebene Link der beste. Welche Grafikklassen interessanter sind, ist schwer zu sagen.

kO(2kn)kO(Logn)

Martin Vatshelle
quelle
Wie Mohammad Al-Turkistany in seiner Antwort sagte, sind kubische ebene Graphen eine jener nicht perfekten Graphen, bei denen unabhängige Mengen angenähert werden können. Alle ebenen Graphen weisen höchstens eine Entartung von 5 auf, und Graphen der Gattung k weisen eine Entartung von O (k) auf, und eine unabhängige Menge kann daher angenähert werden.
Martin Vatshelle
5

Für die Klasse der kubisch-planaren Graphen wird in diesem Artikel ein Algorithmus zur Approximation des Maximum-Independent-Set-Problems in kubisch-planaren Graphen von Elarbi Choukhmane und John Franco vorgestellt, der einen Algorithmus zur Polynom-Zeit-Approximation liefert. Der Näherungsfaktor ihres Algorithmus ist 6/7.

Mohammad Al-Turkistany
quelle
1
Das war bereits durch Bakers Technik (FOCS'83) veraltet, als es 1986 veröffentlicht wurde
David Eppstein
4

Ich habe die Antworten oben nicht überprüft, daher entschuldige ich mich bei Überschneidungen. Hier ist ein spezieller Fall, in dem Sie es genau in Polynomialzeit lösen können. Wenn Ihr Graph G ist ein Liniendiagramm , dann ein Polynom Zeit läuft Algorithmus die Wurzel Graph H, zu finden und dann eine maximale Übereinstimmung in H. finden

Babis Tsourakakis
quelle
Sowohl Liniendiagramme als auch Komplemente von Liniendiagrammen sind polynomisch und werden von der von Suresh Venkat angegebenen Liste abgedeckt.
Martin Vatshelle
3

In geometrischen Schnittgraphen gibt es mehrere interessante Näherungen, PTASs und subexponentielle exakte Algorithmen. Eine Übersicht finden Sie im Wikipedia-Artikel Maximum Disjoint Set .

Erel Segal-Halevi
quelle