Inaproximabilidad de problemas de biclique máximo, corte mínimo y subgrafo al menos denso desde la hipótesis de expansión de conjuntos pequeños
Autores: Manurangsi, Pasin
Idioma: Inglés
Editor: MDPI
Año: 2018
Acceso abierto
Artículo científico
2018
Inaproximabilidad de problemas de biclique máximo, corte mínimo y subgrafo al menos denso desde la hipótesis de expansión de conjuntos pequeños
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Hipótesis de expansión de conjuntos pequeños
NP-difícil
Grafo
Expansión de aristas
Biclique
Subgrafo al menos denso
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 31
Citaciones: Sin citaciones
La Hipótesis de Expansión de Conjunto Pequeño es una conjetura que afirma aproximadamente que es NP-difícil distinguir entre un grafo con un pequeño subconjunto de vértices cuya expansión (de arista) es casi cero y uno en el que todos los pequeños subconjuntos de vértices tienen una expansión casi uno. En este trabajo, demostramos resultados condicionales de inexactitud con ratios esencialmente óptimos para los siguientes problemas de grafos basados en esta hipótesis: Biclique de Borde Máximo, Biclique Balanceado Máximo, Mínimo -Corte y Subgrafo de Al Menos Mayor Densidad. Nuestros resultados de dificultad para los dos problemas de biclique se demuestran combinando una técnica desarrollada por Raghavendra, Steurer y Tulsiani para evitar la localidad de reducciones de gadgets con una generalización de la prueba de código largo de Bansal y Khot, mientras que nuestros resultados para Mínimo -Corte y Subgrafo de Al Menos Mayor Densidad se muestran a través de reducciones elementales.
Descripción
La Hipótesis de Expansión de Conjunto Pequeño es una conjetura que afirma aproximadamente que es NP-difícil distinguir entre un grafo con un pequeño subconjunto de vértices cuya expansión (de arista) es casi cero y uno en el que todos los pequeños subconjuntos de vértices tienen una expansión casi uno. En este trabajo, demostramos resultados condicionales de inexactitud con ratios esencialmente óptimos para los siguientes problemas de grafos basados en esta hipótesis: Biclique de Borde Máximo, Biclique Balanceado Máximo, Mínimo -Corte y Subgrafo de Al Menos Mayor Densidad. Nuestros resultados de dificultad para los dos problemas de biclique se demuestran combinando una técnica desarrollada por Raghavendra, Steurer y Tulsiani para evitar la localidad de reducciones de gadgets con una generalización de la prueba de código largo de Bansal y Khot, mientras que nuestros resultados para Mínimo -Corte y Subgrafo de Al Menos Mayor Densidad se muestran a través de reducciones elementales.