Twardość separatorów wierzchołków

Dla danego wykresu problem separatora pyta, czy istnieje zbiór wierzchołków lub krawędzi o małej liczności (lub wadze), którego usunięcie dzieli G na dwa rozłączne wykresy o w przybliżeniu równych rozmiarach. Nazywa się to problemem separatora wierzchołków, gdy usunięty zestaw jest zestawem wierzchołków, a problemem separatora krawędzi, gdy jest zestawem krawędzi. Oba problemy są NP-kompletne dla ogólnych nieważonych wykresów. Jaka jest najbardziej znana twardość aproksymacji separatora wierzchołków? Czy wykluczono PTAS? Jakie są najbardziej znane wyniki twardości w ukierunkowanym ustawieniu?$G$$G$

Korekta : Poniższe linki i odpowiedzi nie pomogły mi, ponieważ nie zadałem poprawnie pytania. Moje pytanie dotyczy następującego twierdzenia Leightona-Rao:

Twierdzenie : Istnieje algorytm wielomianowy, który, biorąc pod uwagę wykres i zbiór W ⊆ V , znajduje $G(V,E)$$W \subseteq V$ wierzchołek separatoraS⊆VoWwGo rozmiarzeO(szer.Logn), w którymWma wielkość z niewielkiej$\frac{2}{3}$$S \subseteq V$$W$$G$$O(w.{\log}n)$$w$ Separator -Vertex oWwG.$\frac{1}{2}$$W$$G$

Biorąc pod uwagę wykres , a zestaw W ⊆ V , chce się znaleźć δ -Vertex separatora (gdzie $G(V,E)$$W \subseteq V$$\delta$jest stałą) wielkościw, gdziewjest minimalną wielkością$\frac{1}{2} \leq \delta \leq 1$$w$$w$ Separator -Vertex oWwG. Jaka jest najbardziej znana twardość tego problemu? Powyższe twierdzenie podajeprzybliżenieO(logn)dla tego problemu.$\frac{1}{2}$$W$$G$$O({\log}n)$

$|V|/2$

$O(\log n)$

Dobry przegląd znanej pracy nad tym problemem (który łączy się z najrzadszym cięciem, rozpowszechnianiem wskaźników, a nawet unikalną hipotezą gier) znajduje się w najnowszym artykule na temat uogólnień szerokości bisekcji autorstwa Krauthgamera, Naora i Schwartza.

$O(\sqrt{\log n})$$O(\log n)$Leightona i Rao; zrobili to w przypadku krawędzi. Agrawal-Charikar-Makarychev-Makarychev wykorzystał wynik do uzyskania podobnej granicy dla ukierunkowanego cięcia rzadkiego (jeśli ktoś jest zainteresowany cięciami dwuczęściowymi wierzchołków). Feige-Hajiaghayi-Lee w tym samym czasie uzyskał podobne wiązanie ponownie za pomocą ARV dla separatorów wierzchołków (i wskazał również, że szerokość wierzchołka można aproksymować w ramach tego samego współczynnika). Należy zauważyć, że istnieje inne pojęcie rzadkiego cięcia na ukierunkowanych wykresach, dla których Chuzhoy-Khanna wykazał wyniki twardości w przypadku niejednorodnego, ale nie jestem pewien co do jednolitego przypadku. Myślę, że wyniki superstałej twardości są znane z (jednolitego) najrzadszego cięcia pod UGC, ale nie jestem pewien.