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$

cc.complexity-theory np-hardness expanders

— Mohammad Al-Turkistany
źródło

Czy ktoś mógłby wyjaśnić, dlaczego to pytanie jest interesujące? Czy mamy jakieś przykłady problemów trudnych dla NP, które stają się łatwe, gdy ograniczamy się do grafów ekspanderów?

— Jukka Suomela,

@ Jukka: Ekspandery mogą być

nieregularne dla małych

(np.

), ale niektóre problemy trudne dla NP są łatwe w klasie wykresów maksymalnego stopnia

dla małych

(np. KOLOROWANIE WYKRESÓW dla

d

$d$

d

$d$

d = 3

$d=3$

d

$d$

d

$d$

d < 4

$d<4$

— András Salamon,

@ András: Jasne, ale to nie jest tak naprawdę związane z właściwościami rozszerzenia. Pozwólcie, że powtórzę: czy mamy przykłady problemów, które są trudne na wykresach

nieregularnych, ale łatwe na wykresach

regularnych ekspanderów?

d

$d$

d

$d$

— Jukka Suomela,

@Jukka: Wykazano, że unikalne gry mają algorytmy wielomianowego aproksymacji czasu, gdy grafem ograniczenia jest ekspander [Arora-Khot-Kolla-Steurer-Tulsiani-Vishnoi STOC '08]. Nie wiadomo, że tak jest w przypadku grafów ogólnych, a jeśli UGC byłyby prawdziwe, w rzeczywistości nie ma algorytmów wielomianu czasu. Uznałem to za motywację pytania turkistany.

— arnab

@Jukka, moją motywacją jest zrozumienie związku między losowymi właściwościami ekspanderów a twardością obliczeniową problemów. Na przykład nie oczekuję, że niezależny zestaw będzie łatwy dla ekspanderów.

— Mohammad Al-Turkistany

Odpowiedzi:

Jeśli „niezbilansowane ekspandery” liczą się jako ekspandery do celów tego pytania (niezbilansowany ekspander: dwuczęściowy wykres , taki, że dla każdego podzbioru , , ułamek krawędzie między i wynoszą około $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.

— Dana Moshkovitz
źródło

Czy w ostatnim wierszu masz na myśli to, że twój papier konstruuje niezrównoważone ekspandery, ponieważ wtedy możesz mieć odpowiedź na to pytanie: cstheory.stackexchange.com/questions/592/…

— Suresh Venkat

Suresh: tak, papier konstruuje niezrównoważone ekspandery / samplery / ekstraktory, ale nie lepsze niż znane konstrukcje takich.

— Dana Moshkovitz

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 stopnia $G$ o na wierzchołków i dodasz kolejny ekspander na rozłącznych wierzchołkach i umieścisz dopasowanie między i , 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 będzie miało co najwyżej 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 , 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 . 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$

— Boaz Barak
źródło