Dureza dos separadores de vértices

Para um dado gráfico , o Problema do Separador pergunta se existe um conjunto de vértices ou arestas de pequena cardinalidade (ou peso) cuja remoção particiona G em dois gráficos separados de tamanhos aproximadamente iguais. Isso é chamado de Problema do Separador de Vértices quando o conjunto removido é um conjunto de vértices e o Problema do Separador de Borda quando é um conjunto de arestas. Ambos os problemas são NP-completos para gráficos gerais não ponderados. Qual é a dureza mais conhecida da aproximação do separador de vértices? Um PTAS está descartado? Quais são os resultados de dureza mais conhecidos na configuração direcionada?$G$$G$

Correção : Os seguintes links e respostas não me ajudaram porque eu não afirmei minha pergunta corretamente. Minha pergunta está relacionada ao seguinte teorema de Leighton-Rao:

Teorema : Existe um algoritmo de tempo polinomial que, dado um gráfico e um conjunto W ⊆ V , encontra $G(V,E)$$W \subseteq V$Separador de 3 vérticesS⊆VdeWemGde tamanhoO(w.Logn), em quewé o tamanho mínimo de$\frac{2}{3}$$S \subseteq V$$W$$G$$O(w.{\log}n)$$w$ separador -vertex deWemL.$\frac{1}{2}$$W$$G$

Dado um gráfico e um conjunto W ⊆ V , quero encontrar um separador δ- vertex (onde $G(V,E)$$W \subseteq V$$\delta$é uma constante) de tamanhow, em quewé o tamanho mínimo de$\frac{1}{2} \leq \delta \leq 1$$w$$w$ separador -vertex deWemL. Qual é a dureza mais conhecida desse problema? O teorema acima fornece umaaproximaçãoO(logn)para esse problema.$\frac{1}{2}$$W$$G$$O({\log}n)$

$|V|/2$

$O(\log n)$

Uma boa revisão do trabalho conhecido sobre esse problema (que se conecta a cortes mais escassos, espalhando métricas e até mesmo a conjetura de jogos únicos) está neste artigo recente sobre generalizações de largura de bissecção por Krauthgamer, Naor e Schwartz.

$O(\sqrt{\log n})$$O(\log n)$de Leighton e Rao; eles fizeram isso para o caso de ponta. Agrawal-Charikar-Makarychev-Makarychev usou o resultado para obter um limite semelhante para o corte mais esparso direcionado (se alguém estiver interessado em cortes de bipartição de vértice). Feige-Hajiaghayi-Lee, ao mesmo tempo, obteve uma ligação semelhante novamente via ARV para separadores de vértices (e também apontou que a largura da árvore pode ser aproximada dentro do mesmo fator). Deve-se notar que existe outra noção de corte mais esparso nos gráficos direcionados para os quais Chuzhoy-Khanna mostrou resultados de dureza no caso não uniforme, mas não tenho certeza sobre o caso uniforme. Acho que os resultados de dureza super constante são conhecidos pelo corte (uniforme) mais esparso sob UGC, mas não tenho certeza.