Twardość separatorów wierzchołków

11

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 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 , znajduje $G(V,E)$ $W \subseteq V$ wierzchołek separatoraowo rozmiarze, w którymma wielkość z niewielkiej $\frac{2}{3}$ $S \subseteq V$ $W$ $G$ $O(w.{\log}n)$ $w$ Separator -Vertex ow. $\frac{1}{2}$ $W$ $G$

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

$|V|/2$

cc.complexity-theory approximation-hardness

— Shiva Kintali
źródło

1

Zdałem sobie sprawę, że moje poprzednie komentarze były niepotrzebnie ostre. Usunąłem je. W tych komentarzach zostawiam tylko linki: wersję wierzchołka i wersję krawędzi w Kompendium problemów optymalizacji NP.

— Tsuyoshi Ito

Interesuje mnie również to pytanie, czy od tego czasu coś znalazłeś?

— Jarosław Bułatow

@Yaroslav: Nie. Niestety nie udało mi się znaleźć wyników dla tego konkretnego problemu.

— Shiva Kintali,

9

$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.

— Suresh Venkat
źródło

5

$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.

— Chandra Chekuri
źródło