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?
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 2 separador de vérticesS⊆VdeWenGde tamañoO(w.Logn), dondewes el tamaño mínimo de un1 separador -vertex deWenG.
Dado un gráfico y un conjunto W ⊆ V , quiero encontrar un separador de vértices δ (donde 1es una constante) de tamañow, dondewes el tamaño mínimo de un1 separador -vertex deWenG. ¿Cuál es la dureza más conocida de este problema? El teorema anterior da unaaproximaciónO(logn)para este problema.
fuente
Respuestas:
Una buena revisión del trabajo conocido sobre este problema (que se conecta con el corte más escaso, la difusión de métricas e incluso la conjetura de juegos únicos) se encuentra en este reciente artículo sobre generalizaciones del ancho de bisección de Krauthgamer, Naor y Schwartz.
fuente
fuente