There are problems that are NP-Hard on undirected graphs(maximum weight independent set and graph coloring) but are polynomial time solvable on trees. Tree decomposition is a good tool to talk about the ground between a graph and a tree for undirected graphs with notion of treewidth. When graphs are relaxed to bounded treewidth graphs, they give a poly-time solution.
When the graph is directed there are notions like DAG-width, D-width etc. But if we have a problem which is Strongly NP-Hard on DAG and weakly NP-Hard on tree. I want to see what could be on the ground between the DAGs and trees?
Is there a notion of defining the ground between a DAG and a Tree( like bounded treewidth graphs are between a graph and a tree).
I need some pointers if available. I am currently at treewidth generalization for directed graph in this paper.