Testowanie właściwości dla niezależnych zestawów

Załóżmy, że otrzymaliśmy wykres $G$ i parametry $k,\epsilon$. Czy istnieją zakresy wartości dla$k$ (czy jest to wykonalne dla wszystkich $k$), dla których można sprawdzić, czy $G$ jest $\epsilon$-dużo posiadania niezależnego zestawu przynajmniej wielkości $k$ w samą porę $O(n + \text{poly}(1/\epsilon))$ ?

Jeśli użyjemy zwykłego pojęcia $\epsilon$-dale (tj. co najwyżej $\epsilon n^2$krawędzie musiałyby zostać zmienione, aby uzyskać taki zestaw), wtedy problem jest prosty dla . Więc$k = O(n\sqrt{\epsilon})$

• Wydaje się, że jeśli jest większy, niektóre pomysły próbkowania powinny działać w celu rozwiązania problemu. Czy to prawda ?$k$
• Czy istnieją inne pojęcia -far (np. Może zamiast edge ), pod którymi istnieją nietrywialne wyniki?$\epsilon$$\epsilon |E|$

W zasadzie szukam referencji w tym momencie.

Ten problem rzeczywiście został zbadany. Goldreich, Goldwasser i Ron przestudiowali go w swoim przełomowym artykule, który rozpoczął testy właściwości wykresu, a następnie Feige, Langberg i Schechtman również uzyskali wyniki w swoim artykule FOCS '02 „Wykresy z małymi wektorowymi liczbami chromatycznymi i dużymi liczbami chromatycznymi” .

W szczególności [FLS '02] pokazuje, że można rozróżnić wykresy z niezależnym zestawem wielkości $\rho n$ z wykresów $\epsilon$-daleki od bycia takim (co najmniej $\epsilon n^2$ krawędzie należy usunąć, aby utworzyć taki niezależny zestaw), wybierając losowy subgraph wywołany przez $s = \tilde{O}(\rho^4/\epsilon^3)$ losowe wierzchołki na wykresie i sprawdzanie, czy losowy podgraph ma niezależny zestaw wielkości $\rho s$albo nie. ([GGR '98] pokazał słabszą zależność$s$ z $\tilde{O}(\rho/\epsilon^4)$.) [FLS '02] również pokazuje dolną granicę $s$ z $\Omega(\rho^3/\epsilon^2)$.

Inna naturalna definicja $\epsilon$-Zamknięcie do niezależnego zestawu się zmienia $\epsilon k^2$krawędzie Niestety przy tej definicji testowanie właściwości nie wydaje się być rozwiązaniem wielomianowym. Powodem jest to, że nikt nie wie, jak znaleźć posadzoną klikę (i podobnie niezależny zestaw)$o(\sqrt{n})$ wierzchołki na losowym wykresie $n$ wierzchołki szybciej niż $n^{O(\log n)}$czas. Można pokazać, że podgraph, który jest nieco gęstszy niż średnia, może zostać użyty do znalezienia posadzonej kliki w czasie wielomianowym. Jest to dowód na istnienie algorytmu wielomianowego czasu dla tego wariantu problemu$k$ pomiędzy $\log n$ i $\sqrt{n}$.

Referencje: Feige i Krauthgamer. Odnalezienie i poświadczenie dużej ukrytej kliki na wykresie półirandomowym, 1999.