¿Problemas NP-hard en los gráficos de expansión?

En una presentación de 2006 titulada GRÁFICOS DE EXPANDER - ¿HAY MISTERIOS IZQUIERDOS? Nati Linial planteó el siguiente problema abierto:

¿Qué problema computacional de duro en el gráfico sigue siendo difícil cuando se restringe a los gráficos de expansión?$NP$

Desde entonces, ¿se han realizado progresos para probar dicho resultado para un problema de duro?$NP$

Si los "expansores no balanceados" cuentan como expansores para el propósito de esta pregunta (un expansor no balanceado: un gráfico bipartito , de tal manera que para cada subconjunto A ′ ⊆ A , B ′ ⊆ B , la fracción de los bordes entre A ′ y B ′ son aproximadamente | A ′ | | B ′ | / | A | | B $G=(A,B,E)$$A'\subseteq A$$B'\subseteq B$$A'$$B'$${|A'||B'|}/{|A||B|}$), entonces sí, muchos problemas en los expansores (por ejemplo, problemas de satisfacción de restricciones) son NP-difíciles de aproximar.

En particular, la prueba del Teorema de PCP de dos consultas y bajo error [con Ran Raz en 2008] construye gráficos expansores.

Supongo que puede ser fácil mostrar que muchos problemas exactos (y quizás también problemas de aproximación fuertes) son NP-hard en los expansores. La idea es que si tomas un gráfico de grado constante arbitrario en n vértices, y agregas otro expansor H en n vértices disjuntos, y pones una coincidencia entre G y H , entonces obtienes un expansor. La razón es que cualquier conjunto de menos de la mitad de los vértices tendrá una fracción constante de los bordes coincidentes fuera de él, o su intersección con H tendrá como máximo 0,51 fracción de los vértices de $G$$n$$H$$n$$G$$H$$H$$0.51$$H$

Como puede elegir arbitrariamente (por ejemplo, tome un gráfico aleatorio), puede conocer la solución óptima para su problema de NP en H y, por lo tanto, puede haber esperanza (dependiendo del problema) de que, dada una solución para el gráfico combinado, puede obtener al menos una solución aproximada para G . Pero no verifiqué esto para ningún problema concreto.$H$$H$$G$

Por supuesto, como se mencionó anteriormente, hay problemas naturales (especialmente juegos únicos) en los que uno no puede hacer tales trucos y, en particular, los algoritmos son conocidos por los expansores y no se conocen en el caso general. Uno también debería ser capaz de encontrar algún ejemplo artificial de un problema que sea NP difícil en general pero fácil para los expansores (p. Ej., Tome un problema arbitrario de NP difícil en los gráficos y modifíquelo para que todas las instancias con espacio espectral sean más de son YES ...).$1/\log n$