Directed NP-hard problems on DAGs Tree width measures how close a graph is to a tree. Several NP-hard problems are tractable on graphs with bounded tree width. If a problem remains NP-hard on trees then tree width cannot save us. This was the motivation behind one of my previous questions asking for NP-hard problems on trees.

There are several directed versions of tree width measuring how close a directed graph is to a directed acyclic graph (DAG). What are some directed problems that remain NP-hard on DAGs ? A directed problem makes essential use of the directions of the edges. For example, hamiltonian path is a directed problem whereas vertex cover is not. One of the answers to my previous question gave a general recipe for generating problems that are hard on trees. Is there such a recipe for DAGs ?
This only aims at partially answering the first question of the post:


  What are some directed problems that remain NP-hard on DAGs ?


In [1], a few natural problems on directed graphs are given that remain NP-hard on DAGs. The motivation of the paper is to find a "good" treewidth-like measure for digraphs. They argue that the drawback of many measures for digraphs is that they are constant for DAGs, but many directed counterparts of natural problems remain NP-hard on DAGs. For more on this topic, see also [2] and the references of these papers.

[1] Robert Ganian, Petr Hlinený, Joachim Kneis, Alexander Langer, Jan Obdrzálek, Peter Rossmanith: On Digraph Width Measures in Parameterized Algorithmics. IWPEC 2009:185-197. Full version

[2] Robert Ganian, Petr Hlinený, Joachim Kneis, Daniel Meister, Jan Obdrzálek, Peter Rossmanith, Somnath Sikdar: Are there any good digraph width measures?. IPEC 2010, to appear. arXiv