Trudne problemy NP na grafach ekspanderów?

W prezentacji z 2006 r. Zatytułowanej WYKRESY EKSPANDERA - CZY POZOSTAJĄ ŻADNE TAJEMNICE? Nati Linial postawił następujący otwarty problem:

Które -hard obliczeniowa problemu na wykresie pozostają trudne, gdy ogranicza się do wykresów ekspandera?$NP$

Od tego czasu postęp poczyniono udowodnić taki wynik dla -hard problemu?$NP$

Jeśli „niezbilansowane ekspandery” liczą się jako ekspandery do celów tego pytania (niezbilansowany ekspander: dwuczęściowy wykres , taki, że dla każdego podzbioru A ′ ⊆ A , B ′ ⊆ B , ułamek krawędzie między A ′ i B ′ wynoszą około | A ′ | | B ′ | / | A | | B $G=(A,B,E)$$A'\subseteq A$$B'\subseteq B$$A'$$B'$${|A'||B'|}/{|A||B|}$), a więc tak, wiele problemów z ekspanderami (np. problemy z ograniczeniami) są trudne do oszacowania.

W szczególności dowód twierdzenia PCP o dwóch pytaniach i niskim błędzie [z Ran Raz w 2008 r.] Konstruuje wykresy ekspanderów.

Domyślam się, że łatwo jest wykazać, że wiele dokładnych problemów (a być może także silnych problemów z przybliżeniem) jest trudnych do przeprowadzenia na ekspanderze. Chodzi o to, że jeśli weźmiesz dowolny wykres G stopnia$G$ o na wierzchołków i dodasz kolejny ekspander H na n rozłącznych wierzchołkach i umieścisz dopasowanie między G i H , wtedy otrzymasz ekspander. Powodem jest to, że dowolny zestaw mniejszy niż połowa wierzchołków będzie miał albo stały ułamek pasujących krawędzi na zewnątrz, albo jego przecięcie z H będzie miało co najwyżej 0,51 ułamka wierzchołków $n$$H$$n$$G$$H$$H$$0.51$$H$

Ponieważ możesz wybrać dowolnie (np. Weź losowy wykres), możesz znać optymalne rozwiązanie swojego problemu NP w H , a zatem może być nadzieja (w zależności od problemu), że biorąc pod uwagę rozwiązanie dla połączonego wykresu, możesz uzyskać co najmniej w przybliżeniu w roztworze G . Ale nie zweryfikowałem tego pod kątem żadnego konkretnego problemu.$H$$H$$G$

Oczywiście, jak wspomniano powyżej, istnieją naturalne problemy (przede wszystkim unikalne gry), w których nie można wykonywać takich sztuczek, a w szczególności algorytmy są znane dla ekspanderów i nie są znane w ogólnym przypadku. Należy również wymyślić jakiś wymyślony przykład problemu, który ogólnie jest trudny do NP, ale łatwy w ekspanderach (np. Weź jakiś trudny NP problem do grafów i zmodyfikuj go tak, aby wszystkie wystąpienia z odstępem widmowym większym niż są TAK ...).$1/\log n$