El ancho del árbol mide qué tan cerca está un gráfico de un árbol. Varios problemas NP-hard son manejables en gráficos con ancho de árbol acotado. Si un problema sigue siendo NP-hard en los árboles, entonces el ancho del árbol no puede salvarnos. Esta fue la motivación detrás de una de mis preguntas anteriores sobre los problemas NP-difíciles en los árboles.
Existen varias versiones dirigidas del ancho del árbol que miden qué tan cerca está un gráfico dirigido de un gráfico acíclico dirigido (DAG). ¿Cuáles son algunos problemas dirigidos que siguen siendo NP-hard en los DAG? Un problema dirigido hace uso esencial de las direcciones de los bordes. Por ejemplo, el camino hamiltoniano es un problema dirigido, mientras que la cobertura de vértices no lo es. Una de las respuestas a mi pregunta anterior dio una receta general para generar problemas que son difíciles para los árboles. ¿Existe tal receta para los DAG?
fuente
El famoso problema OPEN [8] de la lista de Garey y Johnson está más allá de P, pero está abierto a ser demostrado que es NP-C. Ese problema está en DAG. Cada ronda puede eliminar a lo sumo tres vértices que no tienen borde entrante. ¿Decidir si todos los vértices del DAG podrían eliminarse en rondas K? Abierto desde 1970.
fuente