Problemas NP-difíceis em gráficos de expansão?

Em uma apresentação de 2006 intitulada GRÁFICOS DE EXPANSOR - EXISTEM MISTÉRIOS DEIXADOS? , Nati Linial colocou o seguinte problema em aberto:

Que -Hard problema computacional no gráfico permanecem difícil quando restrita aos gráficos de expansão?$NP$

Desde então, tem algum progresso foi feito para provar esse resultado para um problema -Hard?$NP$

Se "expansores desequilibradas" contam como expansores para o propósito desta questão (um expansor desequilibrada: um bipartido gráfico , de tal modo que para cada sub-grupos A ' ⊆ A , B ' Ç B , a fracção de arestas entre A ′ e B ′ é de cerca de | A ′ | | B ′ | / | A | | B $G=(A,B,E)$$A'\subseteq A$$B'\subseteq B$$A'$$B'$${|A'||B'|}/{|A||B|}$), sim, muitos problemas nos expansores (por exemplo, problemas de satisfação com restrições) são difíceis de aproximar.

Em particular, a prova do Teorema PCP de duas consultas e baixo erro constrói gráficos de expansão.

Estou supondo que pode ser fácil mostrar que muitos problemas exatos (e talvez fortes problemas de aproximação também) são difíceis de usar nos expansores. A idéia é que, se você pegar um gráfico arbitrário de graus constantes em n vértices e adicionar outro expansor H em n vértices separados, e colocar uma correspondência entre G e H , obterá um expansor. A razão é que qualquer conjunto com menos da metade dos vértices terá uma fração constante das arestas correspondentes fora dele ou sua interseção com H terá, no máximo, 0,51 fração dos vértices de $G$$n$$H$$n$$G$$H$$H$$0.51$$H$

Como você pode escolher arbitrariamente (digamos, pegar um gráfico aleatório), você pode conhecer a solução ideal para o seu problema NP em H e, portanto, pode haver esperança (dependendo do problema), que, dada uma solução para o gráfico combinado, você pode obter pelo menos uma solução aproximada para L . Mas não verifiquei isso por nenhum problema concreto.$H$$H$$G$

Obviamente, como mencionado acima, existem problemas naturais (principalmente jogos únicos) em que não se pode fazer esses truques e, em particular, algoritmos são conhecidos por expansores e não são conhecidos no caso geral. Também é possível encontrar um exemplo artificial de um problema que é difícil de NP em geral, mas fácil em expansores (por exemplo, pegue alguns problemas difíceis arbitrários de NP em gráficos e modifique-o para que todas as instâncias com intervalo espectral sejam maiores que são SIM ...).$1/\log n$