El problema de corte máximo es un problema NP-difícil que no puede ser resuelto en tiempo polinomial salvo que P=NP. Una de las características interesantes de este problema es que se ha demostrado que la mejor cota de ...