Em todos os lugares que eu li sobre o problema de corte mais escasso, ele diz apenas que o problema é conhecido por ser NP- difícil. Onde posso encontrar uma prova disso? Qual problema NP- duro conhecido reduz ao problema de corte mais esparso?
Não encontrei nenhuma prova no livro de Vazirani - Algoritmos de Aproximação, que apresenta o algoritmo Leighton Rao, ou no livro "Computers and Intratability" - que resume muitos problemas completos de NP . Não consegui encontrá-lo pesquisando (com cadeias de pesquisa óbvias) no Google. Há um artigo de Chawla et al., Que assume a conjectura de Khot no UGC e comprova a dureza de se aproximar do corte mais escasso. Eu esperava ver uma prova que não assuma nenhuma conjectura.
A prova deve apenas reduzir um problema NP- duro conhecido a um corte mais esparso.
Obrigado,
Arpita Korwar.
fonte
Respostas:
[Movido do comentário]
O artigo " Cortes mais escassos e gargalos nos gráficos ", de David W. Matula, Farhad Shahrokhi, reduz o problema do corte máximo. A prova de dureza da Max-cut pode ser encontrada em Garey Johnson.
fonte