Me encontré con el siguiente problema:
Dado un gráfico acíclico dirigido con pesos de arista con valores reales y dos vértices syt, calcule el corte st mínimo.
Para gráficos generales, esto es NP-hard, ya que uno puede reducir trivialmente el corte máximo simplemente invirtiendo los pesos de los bordes (corrígeme si me equivoco).
¿Cuál es la situación con los DAG? ¿Se puede resolver el corte mínimo (o corte máximo) en tiempo polinómico? ¿Es NP-hard y, de ser así, hay algún algoritmo de aproximación conocido?
Traté de encontrar trabajo en esto pero no pude (tal vez solo estoy usando palabras clave incorrectas en mis búsquedas), así que esperaba que alguien supiera (o encontrara) algo sobre esto.
Respuestas:
fuente