Dureza de los separadores de vértices

11

Para un gráfico dado , el Problema del separador pregunta si existe un conjunto de vértices o bordes de pequeña cardinalidad (o peso) cuya eliminación separa G en dos gráficos disjuntos de tamaños aproximadamente iguales. Esto se llama el Problema del separador de vértices cuando el conjunto eliminado es un conjunto de vértices y el Problema del separador de bordes cuando es un conjunto de bordes. Ambos problemas son NP completos para gráficos generales no ponderados. ¿Cuál es la dureza más conocida del separador de vértices aproximado? ¿Se descarta un PTAS? ¿Cuáles son los resultados de dureza más conocidos en la configuración dirigida?GG

Corrección : Los siguientes enlaces y respuestas no me ayudaron porque no dije mi pregunta correctamente. Mi pregunta está relacionada con el siguiente teorema de Leighton-Rao:

Teorema : existe un algoritmo de tiempo polinómico que, dado un gráfico y un conjunto W V , encuentra un 2G(V,E)WV separador de vérticesSVdeWenGde tamañoO(w.Logn), dondewes el tamaño mínimo de un123SVWGO(w.logn)w separador -vertex deWenG.12WG

Dado un gráfico y un conjunto W V , quiero encontrar un separador de vértices δ (donde 1G(V,E)WVδes una constante) de tamañow, dondewes el tamaño mínimo de un112δ1ww separador -vertex deWenG. ¿Cuál es la dureza más conocida de este problema? El teorema anterior da unaaproximaciónO(logn)para este problema.12WGO(logn)

|V|/2

Shiva Kintali
fuente
1
Me di cuenta de que mis comentarios anteriores eran innecesariamente duros. Me los quité. Solo dejo enlaces en esos comentarios: la versión de vértice y la versión de borde en el Compendio de problemas de optimización de NP.
Tsuyoshi Ito
También me interesa esta pregunta, ¿encontraste algo desde entonces?
Yaroslav Bulatov
@Yaroslav: No. Desafortunadamente no pude encontrar ningún resultado de dureza para este problema en particular.
Shiva Kintali

Respuestas:

5

O(logn)O(logn)de Leighton y Rao; hicieron esto para el caso límite. Agrawal-Charikar-Makarychev-Makarychev utilizó el resultado para obtener un límite similar para el corte más disperso dirigido (si uno está interesado en los cortes de bipartición de vértice). Feige-Hajiaghayi-Lee al mismo tiempo obtuvo un límite similar nuevamente a través de ARV para los separadores de vértices (y también señaló que el ancho del árbol puede aproximarse dentro del mismo factor). Cabe señalar que existe otra noción de corte más escaso en los gráficos dirigidos para los cuales Chuzhoy-Khanna mostró resultados de dureza en el caso no uniforme, pero no estoy seguro sobre el caso uniforme. Creo que los resultados de dureza súper constante son conocidos por el corte más escaso (uniforme) bajo UGC, pero no estoy seguro.

Chandra Chekuri
fuente