Härte von Vertex-Separatoren

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?$G$$G$

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 $G(V,E)$$W \subseteq V$ ScheitelpunkttrennerS⊆VvonWinGder GrößeO(w.Logn), wobeiwdie Mindestgröße einer$\frac{2}{3}$$S \subseteq V$$W$$G$$O(w.{\log}n)$$w$ -eckiges Separator vonWinG.$\frac{1}{2}$$W$$G$

Wenn ein Graph und eine Menge W ⊆ V gegeben sind , möchte ich einen δ- Vertex-Separator finden (wobei $G(V,E)$$W \subseteq V$$\delta$ist eine Konstante) der Größew, wobeiwdie minimale Größe einer$\frac{1}{2} \leq \delta \leq 1$$w$$w$ -eckiges Separator vonWinG. Was ist die bekannteste Härte dieses Problems? Der obige Satz gibt eineO(logn)-Näherung für dieses Problem an.$\frac{1}{2}$$W$$G$$O({\log}n)$

$|V|/2$

$O(\log n)$

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.

$O(\sqrt{\log n})$$O(\log n)$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.