cc.complexity-theory – Prueba de que el corte más escaso es NP-hard

Pregunta:

En todas partes que leo sobre el problema del corte más disperso, 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 intratabilidad" – que resume muchos problemas NP completos. No pude encontrarlo buscando (con cadenas de búsqueda obvias) en Google. Hay un artículo de Chawla et al, que asume la conjetura de UGC de Khot y demuestra la dureza de aproximarse al corte más escaso. Esperaba ver una prueba que no suponga ninguna conjetura.

La prueba debería simplemente reducir un problema NP- duro conocido al corte más escaso.

Gracias,

Arpita Korwar.

Respuesta:

[Movido del comentario]

El artículo " Los cortes más escasos y los 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.

Leave a Comment

Your email address will not be published.

Scroll to Top

istanbul avukat

-

web tasarım