Esta es una tarea del concurso de TI alemán ("Bundeswettbewerb Informatik"), pero dado que la fecha límite ha pasado, hacer esta pregunta no es trampa.
Dado un gráfico dirigido ponderado por vértices y valores , encuentre un subconjunto de nodos que maximice sujeto a ¿Es este problema NP-hard?
Podría demostrar que el problema está en P si cada nodo no tiene padres o hijos mostrando que en este caso, Vertex Cover puede resolverlo en gráficos bipartitos, pero no pude encontrar una reducción que pruebe la dureza NP del problema original
¿Alguien puede darme una pista de cómo hacer esto?
PD: En el concurso, la tarea era solo encontrar un algoritmo que resuelva este problema, la definición original (alemana) es la tarea 1 de este documento: http://www.bundeswettbewerb-informatik.de/fileadmin/templates/bwinf/ aufgaben / bwinf35 / aufgaben352.pdf
fuente
Respuestas:
El problema es solucionable en tiempo polinómico, sugerido en el Lema 1 del artículo Complejidad computacional de algunos problemas de peso promedio máximo con restricciones de precedencia .
Básicamente, la idea es escribir un programa lineal en las variables , donde si . La matriz de adyacencia firmada es totalmente unimodular, por lo que podemos calcular el óptimo integral.Xyo∈ [ 0 , 1 ] Xtu-Xv≤ 0 ( u , v ) ∈ E
fuente