Estou vendo a página 28 de Lovasz "Programas semidefinidos e otimização combinatória" e fornece a seguinte aproximação do número de independência do gráfico
sujeito a
Posso obter um conjunto independente (ou algo próximo a um conjunto independente) diretamente da solução de relaxamento do SDP? Lovasz diz que o SDP é a única maneira conhecida de resolver esse problema exatamente para gráficos perfeitos, isso ainda é verdade?
Esclarecimento: existe um relaxamento SDP semelhante para o tamanho do corte máximo, e eu posso obter a solução completa (o corte real, e não o tamanho), pegando a raiz quadrada de Z e fazendo o arredondamento aleatório (cap.6 do livro Williamson / Shmoys) ) Gostaria de saber se existe uma técnica semelhante para este problema
ds.algorithms
graph-theory
semidefinite-programming
independent-set
Yaroslav Bulatov
fonte
fonte
Respostas:
Acredito que o SDP é a única técnica conhecida para resolver o problema do conjunto independente máximo em gráficos perfeitos. Para obter o conjunto independente, pode-se fazer o seguinte. Adivinhe se um vértice está no conjunto independente, exclua-o e resolva o SDP. Se retornar o mesmo valor, haverá um conjunto independente sem esse vértice. Portanto, faça esse vértice adjacente a todos os outros vértices e continue. Isso deve fornecer um conjunto independente real.
Caso contrário, identificamos um vértice do conjunto independente e podemos removê-lo e continuar no gráfico restante.
fonte
Não tenho certeza se o comentário de Lovasz ainda é válido. Houve alguns trabalhos recentes sobre este (e relacionados) problemas em gráficos perfeitos. Você deve dar uma olhada no link a seguir para técnicas que envolvem a passagem de mensagens em vez de resolver SDPs: http://www.cs.columbia.edu/~jebara/papers/uai09perfect.pdf
fonte