Teste de propriedade para conjuntos independentes

9

Suponha que recebamos um gráfico G e os parâmetros k,ϵ . Existem intervalos de valores para k (ou é possível para todos os k ) para os quais é possível testar se G é ϵ - longe de ter um conjunto independente de tamanho pelo menos k no tempo O(n+poly(1/ϵ)) ?

Se usarmos a noção usual de -far (ou seja, no máximo ϵ n 2 arestas precisariam ser alteradas para obter esse conjunto), então o problema é trivial para k = O ( n ϵϵn2. assimk=O(nϵ)

  • Parece que se for maior, algumas idéias de amostragem devem funcionar para resolver o problema. Isso é verdade ?k
  • Existem outras noções de -far (por exemplo, talvez ϵ | E | edge) sob as quais existem resultados não triviais?ϵϵ|E|

Eu estou basicamente procurando por referências neste momento.

Suresh Venkat
fonte

Respostas:

10

Este problema foi realmente estudado. Goldreich, Goldwasser e Ron o estudaram em seu trabalho seminal, que iniciou os testes de propriedades gráficas. Feige, Langberg e Schechtman também obtiveram resultados em seu trabalho da FOCS '02 "Gráficos com pequenos números cromáticos vetoriais e grandes números cromáticos" .

Especificamente, [FLS '02] mostra que é possível distinguir entre gráficos com um conjunto independente de tamanho dos gráficos far - muito menos que isso (o que significa que pelo menos ϵ n 2 arestas precisam ser removidas para criar um conjunto independente) escolhendo um subgráfico aleatório induzido por s = ˜ O ( ρ 4 / ϵ 3 ) vértices aleatórios no gráfico e verificando se o subgráfico aleatório tem um conjunto independente de tamanho ρ s ou não. ([GGR '98] mostrou um limite mais fraco em s de ˜ O ( ρ /ρnϵϵn2s=O~(ρ4/ϵ3)ρss .) [FLS '02] também mostra um limite inferior em s de Ω ( ρ 3 / ϵ 2 ) .O~(ρ/ϵ4)sΩ(ρ3/ϵ2)

arnab
fonte
6

Outra definição natural de -close a um conjunto independente está mudando ε k 2 bordas. Infelizmente, com esta definição, o teste de propriedade não parece ser polinomial em tempo de solução. A razão é que ninguém sabe como encontrar uma camarilha plantada (e um conjunto igualmente independente) de o ( ϵϵk2o(n)nnO(logn)klognn

Referência: Feige e Krauthgamer. Localizando e certificando uma grande clique oculta em um gráfico semi-aleatório, 1999.

Warren Schudy
fonte