Algoritmos de aproximação para o Conjunto Independente Máximo em classes especiais de gráficos

Sabemos que é difícil aproximar o Conjunto Independente Máximo (MIS) dentro de um fator de para qualquer menos que P = NP. Quais são algumas classes especiais de gráficos para as quais são conhecidos melhores algoritmos de aproximação?$n^{1-\epsilon}$$\epsilon > 0$

Quais são os gráficos pelos quais os algoritmos de tempo polinomial são conhecidos? Eu sei que para gráficos perfeitos isso é conhecido, mas existem outras classes interessantes de gráficos?

Existe uma lista realmente impressionante de todas as classes gráficas conhecidas que possuem algoritmos não triviais para o MIS: consulte esta entrada no site das classes gráficas.

Não tenho uma boa visão geral desse problema, mas posso dar alguns exemplos. Um algoritmo de aproximação simples seria encontrar uma ordem dos nós e selecionar avidamente os nós que estão no conjunto independente se nenhum de seus vizinhos anteriores tiver sido selecionado no conjunto independente.

$d$$d$$n^{1-\epsilon}$

Existem algumas outras técnicas para aproximações que também funcionam, mas eu não as conheço bem. Veja: http://en.wikipedia.org/wiki/Baker%27s_technique e http://courses.engr.illinois.edu/cs598csc/sp2011/Lectures/lecture_7.pdf

Para os algoritmos polinomiais que resolvem exatamente os problemas O link fornecido por Suresh é o melhor. Quais classes de gráficos mais interessantes são difíceis de dizer.

$k$$O(2^k n)$$k$$O(\log n)$

Para a classe de gráficos planares cúbicos, este artigo, Um algoritmo de aproximação para o problema de conjunto independente máximo em gráficos planares cúbicos de Elarbi Choukhmane e John Franco, fornece um algoritmo de aproximação de tempo polinomial. O fator de aproximação de seu algoritmo é 6/7.

Eu não verifiquei as respostas acima, então peço desculpas se houver uma sobreposição. Aqui está um caso especial em que você pode resolvê-lo exatamente em tempo polinomial. Se o seu gráfico G for um gráfico de linhas , execute um algoritmo de tempo polinomial para encontrar o gráfico raiz H e, em seguida, encontre uma correspondência máxima em H.

Nos gráficos de interseção geométrica, existem várias aproximações interessantes, PTASs e algoritmos exatos sub-exponenciais. Consulte o artigo da Wikipedia Conjunto Máximo Disjoint para uma pesquisa.