Härte von Vertex-Separatoren

11

Für einen gegebenen Graphen fragt das Separatorproblem, ob ein Scheitelpunkt oder eine Kantenmenge mit kleiner Kardinalität (oder Gewichtung) existiert, deren Entfernungspartitionen G in zwei disjunkte Graphen von ungefähr gleicher Größe unterteilt sind. Dies wird als Vertex Separator Problem bezeichnet, wenn die entfernte Menge eine Vertexmenge ist, und als Edge Separator Problem, wenn es sich um eine Kantenmenge handelt. Beide Probleme sind für allgemeine ungewichtete Graphen NP-vollständig. Was ist die bekannteste Härte des approximierenden Scheitelpunkttrenners? Ist ein PTAS ausgeschlossen? Was sind die bekanntesten Härteergebnisse in der gerichteten Einstellung?GG

Korrektur : Die folgenden Links und Antworten haben mir nicht geholfen, da ich meine Frage nicht richtig angegeben habe. Meine Frage bezieht sich auf den folgenden Satz von Leighton-Rao:

Satz : Es gibt einen Polynomzeitalgorithmus, der bei gegebenem Graphen und einer Menge W V eine 2 findetG(V,E)WV ScheitelpunkttrennerSVvonWinGder GrößeO(w.Logn), wobeiwdie Mindestgröße einer1 ist23SVWGO(w.logn)w -eckiges Separator vonWinG.12WG

Wenn ein Graph und eine Menge W V gegeben sind , möchte ich einen δ- Vertex-Separator finden (wobei 1G(V,E)WVδist eine Konstante) der Größew, wobeiwdie minimale Größe einer1 ist12δ1ww -eckiges Separator vonWinG. Was ist die bekannteste Härte dieses Problems? Der obige Satz gibt eineO(logn)-Näherung für dieses Problem an.12WGO(logn)

|V|/2

Shiva Kintali
quelle
1
Mir wurde klar, dass meine vorherigen Kommentare unnötig hart waren. Ich habe sie entfernt. Ich lasse nur Links in diesen Kommentaren: die Vertex-Version und die Edge-Version im Kompendium der NP-Optimierungsprobleme.
Tsuyoshi Ito
Diese Frage interessiert mich auch. Haben Sie seitdem etwas gefunden?
Jaroslaw Bulatow
@ Jaroslaw: Nein. Leider konnte ich für dieses spezielle Problem keine Härteergebnisse finden.
Shiva Kintali

Antworten:

9

O(logn)

Eine gute Übersicht über die bekannten Arbeiten zu diesem Problem (die mit dem spärlichsten Schnitt, den Ausbreitungsmetriken und sogar der einzigartigen Spielvermutung in Verbindung stehen) findet sich in diesem kürzlich erschienenen Artikel über Verallgemeinerungen der Halbierungsbreite von Krauthgamer, Naor und Schwartz.

Suresh Venkat
quelle
5

O(logn)O(logn)von Leighton und Rao; Sie haben dies für den Randfall getan. Agrawal-Charikar-Makarychev-Makarychev verwendete das Ergebnis, um eine ähnliche Grenze für den gerichteten, spärlichsten Schnitt zu erhalten (wenn man an Schnitten mit zwei Scheitelpunkten interessiert ist). Feige-Hajiaghayi-Lee erhielt gleichzeitig erneut eine ähnliche Bindung über ARV für Scheitelpunkttrenner (und wies auch darauf hin, dass die Baumbreite innerhalb desselben Faktors angenähert werden kann). Man sollte beachten, dass es einen anderen Begriff des spärlichsten Schnitts in gerichteten Graphen gibt, für den Chuzhoy-Khanna im ungleichmäßigen Fall Härteergebnisse zeigte, aber ich bin mir über den einheitlichen Fall nicht sicher. Ich denke, dass superkonstante Härteergebnisse für (gleichmäßige) spärlichste Schnitte unter UGC bekannt sind, aber ich bin mir nicht sicher.

Chandra Chekuri
quelle