NP-сложные проблемы на графах расширителей?

В презентации 2006 года под названием EXPANDER GRAPHS - ОСТАЮТСЯ ЛИ какие-то ТАЙНЫ? Нати Линиал поставил следующую открытую проблему:

Какие трудные вычислительные задачи на графе остаются сложными, когда они ограничены графами расширителей?$NP$

С тех пор был ли достигнут какой-либо прогресс в доказательстве такого результата для трудной задачи?$NP$

Если «неуравновешенные расширители» считаются расширителями для целей этого вопроса (неуравновешенный расширитель: двудольный граф , такой что для каждого подмножества A ′ ⊆ A , B ′ ⊆ B , доля ребра между A ′ и B ′ составляют около | A ′ | | B ′ | / | A | | B $G=(A,B,E)$$A'\subseteq A$$B'\subseteq B$$A'$$B'$${|A'||B'|}/{|A||B|}$), то да, многие проблемы на расширителях (например, проблемы удовлетворения ограничений) трудно поддаются аппроксимации.

В частности, доказательство теоремы PCP с двумя запросами с малой ошибкой [совместно с Ран Рацем в 2008 году] строит графы расширителей.

Я предполагаю, что может быть легко показать, что многие точные задачи (и, возможно, проблемы сильных приближений) NP-трудны для расширителей. Идея состоит в том, что если вы возьмете произвольный граф степеней на n вершин и добавите еще один расширитель H на n непересекающихся вершин, и поместите соответствие между G и H , то вы получите расширитель. Причина в том, что любой набор, содержащий менее половины вершин, будет иметь либо постоянную долю совпадающих ребер вне его, либо его пересечение с H будет иметь, как правило, не более 0,51 доли вершин $G$$n$$H$$n$$G$$H$$H$$0.51$$H$

Поскольку вы можете выбрать произвольно (скажем, взять случайный граф), вы можете знать оптимальное решение для вашей задачи NP в H , и, следовательно, может быть надежда (в зависимости от проблемы), что при решении для комбинированного графа вы можете получить по меньшей мере , приближенное решение для G . Но я не проверял это ни для какой конкретной проблемы.$H$$H$$G$

Конечно, как упомянуто выше, существуют естественные проблемы (особенно уникальные игры), когда нельзя делать такие трюки, и, в частности, алгоритмы известны для расширителей и не известны в общем случае. Нужно также иметь возможность придумать какой-нибудь надуманный пример задачи, которая является NP сложной в общем случае, но простой для расширителей (например, взять некоторую произвольную сложную задачу NP на графах и изменить ее так, чтобы все случаи со спектральным зазором более являются ДА ...).$1/\log n$