NP-harte Probleme bei Expandergraphen?

In einer Präsentation von 2006 mit dem Titel EXPANDER GRAPHS - GIBT ES NOCH GEHEIMNISSE? Nati Linial stellte das folgende offene Problem:

Welches -harte Rechenproblem im Graphen bleibt schwierig, wenn es auf Expandergraphen beschränkt ist?$NP$

Seitdem hat sich bisher keine Fortschritte gemacht solches Ergebnis für einen zu beweisen , -hard Problem?$NP$

Wenn "unsymmetrische Expander" im Sinne dieser Frage als Expander gelten (ein unsymmetrischer Expander: ein zweigliedriger Graph , so dass für jede Teilmenge A ' ⊆ A , B ' ⊆ B der Bruchteil von Kanten zwischen A ' und B ' sind etwa | A ' | | B ' | / | A | | B $G=(A,B,E)$$A'\subseteq A$$B'\subseteq B$$A'$$B'$${|A'||B'|}/{|A||B|}$), dann sind viele Probleme bei Expandern (z. B. Bedingungszufriedenheitsprobleme) schwer zu approximieren.

Insbesondere der Beweis des PCP-Theorems mit zwei Abfragen und geringem Fehler [mit Ran Raz im Jahr 2008] konstruiert Expandergraphen.

Vermutlich ist es einfach zu zeigen, dass viele exakte Probleme (und möglicherweise auch starke Approximationsprobleme) für Expander NP-schwer sind. Die Idee ist, dass, wenn Sie einen beliebigen Graphen konstanten Grades auf n Eckpunkten nehmen und einen weiteren Expander H auf n disjunkten Eckpunkten hinzufügen und eine Übereinstimmung zwischen G und H setzen , Sie einen Expander erhalten. Der Grund dafür ist, dass jede Menge von weniger als der Hälfte der Scheitelpunkte entweder einen konstanten Bruchteil der übereinstimmenden Kanten außerhalb der Scheitelpunkte aufweist oder dass ihr Schnittpunkt mit H höchstens 0,51 Bruchteil der Scheitelpunkte von H aufweist .$G$$n$$H$$n$$G$$H$$H$$0.51$$H$

Da Sie willkürlich wählen können (sagen wir, nehmen Sie einen zufälligen Graphen), können Sie die optimale Lösung für Ihr NP-Problem in H kennen , und daher kann (abhängig vom Problem) die Hoffnung bestehen, dass Sie eine Lösung für den kombinierten Graphen erhalten mindestens eine Näherungslösung für G . Aber ich habe dies nicht auf ein konkretes Problem überprüft.$H$$H$$G$

Natürlich gibt es, wie oben erwähnt, natürliche Probleme (insbesondere einzigartige Spiele), bei denen man solche Tricks nicht ausführen kann, und insbesondere sind Algorithmen für Expander bekannt und im allgemeinen Fall nicht bekannt. Man sollte auch in der Lage sein , mit etwas gekünstelt Beispiel für ein Problem zu finden, die im Allgemeinen NP schwer ist , aber leicht auf Expander (zB nehmen Sie sich etwas willkürlich NP hart Problem auf Graphen, und ändern Sie es so , dass alle Instanzen mit Spektrallücke mehr als sind JA ...).$1/\log n$