En todas partes que leí sobre el problema de corte más escaso, solo dice que se sabe que el problema es NP- duro. ¿Dónde puedo encontrar una prueba de esto? ¿Qué problema NP- duro conocido se reduce al problema de corte más escaso?
No pude encontrar ninguna prueba en el libro de Vazirani - Algoritmos de aproximación, que presenta el algoritmo de Leighton Rao, o el libro "Computadoras e Intractabilidad" - que resume muchos NP completos de . No pude encontrarlo buscando (con cadenas de búsqueda obvias) en Google. Hay un artículo de Chawla et al, que asume la conjetura UGC de Khot y demuestra la dureza de aproximar el corte más escaso. Esperaba ver una prueba que no suponga ninguna conjetura.
La prueba solo debe reducir un problema conocido de NP- duro al corte más escaso.
Gracias,
Arpita Korwar.
fuente
Respuestas:
[Movido del comentario]
El artículo " Cortes más dispersos y cuellos de botella en los gráficos " de David W. Matula, Farhad Shahrokhi, ofrece una reducción del problema de corte máximo. La prueba de dureza de Max-cut se puede encontrar en Garey Johnson.
fuente