Problèmes NP-difficiles sur les graphiques d'extension?

Dans une présentation de 2006 intitulée EXPANDER GRAPHS - Y A-T-IL DES MYSTÈRES À GAUCHE? , Nati Linial a posé le problème ouvert suivant:

Quel problème de calcul dur sur le graphique reste difficile lorsqu'il est limité aux graphiques d'extension?$NP$

Depuis lors, des progrès ont-ils été accomplis pour prouver un tel résultat pour un problème dur?$NP$

Si les "expandeurs non équilibrés" comptent comme des expandeurs pour les besoins de cette question (un expandeur non équilibré: un graphe biparti , de sorte que pour chaque sous-ensemble , , le la fraction des arêtes entre et est d'environ ), alors oui, de nombreux problèmes sur les expandeurs (par exemple, problèmes de satisfaction des contraintes) sont NP-difficiles approximer.$G=(A,B,E)$$A'\subseteq A$$B'\subseteq B$$A'$$B'$${|A'||B'|}/{|A||B|}$

En particulier, la preuve du théorème PCP à deux requêtes et à faible erreur [avec Ran Raz en 2008] construit des graphiques d'expansion.

J'imagine qu'il peut être facile de montrer que de nombreux problèmes exacts (et peut-être aussi de forts problèmes d'approximation) sont NP-difficiles pour les expandeurs. L'idée est que si vous prenez un graphe de degré constant arbitraire sur n sommets, et ajoutez un autre extenseur H sur n sommets disjoints, et mettez une correspondance entre G et H , alors vous obtenez un expanseur. La raison en est que tout ensemble de moins de la moitié des sommets aura soit une fraction constante des arêtes correspondantes à l'extérieur, soit son intersection avec H aura au plus disons 0,51 fraction des sommets de $G$$n$$H$$n$$G$$H$$H$$0.51$$H$

Puisque vous pouvez choisir arbitrairement (par exemple, prenez un graphique aléatoire), vous pouvez connaître la solution optimale pour votre problème NP dans H , et donc il peut y avoir de l'espoir (selon le problème), que, étant donné une solution pour le graphique combiné, vous pouvez obtenir au moins une solution approchée pour G . Mais je n'ai vérifié cela pour aucun problème concret.$H$$H$$G$

Bien sûr, comme mentionné ci-dessus, il existe des problèmes naturels (notamment des jeux uniques) où l'on ne peut pas faire de telles astuces et en particulier les algorithmes sont connus pour les expanseurs et ne sont pas connus dans le cas général. On devrait également être en mesure de trouver un exemple artificiel d'un problème qui est NP difficile en général mais facile sur les expandeurs (par exemple, prendre un problème dur NP arbitraire sur les graphiques et le modifier de sorte que toutes les instances avec un écart spectral supérieur à est OUI ...).$1/\log n$