logo móvil
Contáctanos

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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro