<p>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. </p>

<p>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? </p>

<p>Is there a notion of defining the <strong>ground</strong> between a DAG and a Tree( like bounded treewidth graphs are between a graph and a tree).  </p>

<p>I need some pointers if available. I am currently at treewidth generalization for directed graph in this <a href="https://ac.els-cdn.com/S0095895600920318/1-s2.0-S0095895600920318-main.pdf?_tid=cd73416f-cd37-419d-b8b5-a6d7d20f83f5&amp;acdnat=1529610311_9e21a5a465b78cc26929d0cd67c007b0" rel="nofollow noreferrer">paper</a>. </p>

CC BY-SA 4.0
2018-06-22T00:08:15.463Z
You may want to see also the paper on DAG width. https://www.sciencedirect.com/science/article/pii/S0095895612000329
Chandra Chekuri
CC BY-SA 4.0
2018-06-22T14:01:53.643Z
You could also consider the less technical notion of counting the number of edges that have to removed from the underlying undirected graph of the DAG, in order to turn that into a tree.
Bart Jansen
CC BY-SA 4.0
2018-06-23T00:06:19.100Z
DAGs and trees are not close together. There are many problems which are hard on DAGs and easy on trees (more generally they are easy on class of digraps where their underlying undirected graph is of bounded treewidth).
Saeed
CC BY-SA 4.0
2018-07-09T04:57:53.537Z
@ChandraChekuri  But the problem I am considering is on a DAG. The DAG width for DAG would be 1. So DAG width isn’t of much relevance to the problem, apparently.
am_rf24
<reference-request><np-hardness><directed-acyclic-graph><treewidth>
Directed NP Hard Problem on DAG
am_rf24
# Directed NP Hard Problem on DAG

(Asked by: username_0 on 2018-06-21)

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](https://ac.els-cdn.com/S0095895600920318/1-s2.0-S0095895600920318-main.pdf?_tid=cd73416f-cd37-419d-b8b5-a6d7d20f83f5&acdnat=1529610311_9e21a5a465b78cc26929d0cd67c007b0).

**Tags:** reference-request, np-hardness, directed-acyclic-graph, treewidth

> **Comments:**
> **username_1**: You may want to see also the paper on DAG width. https://www.sciencedirect.com/science/article/pii/S0095895612000329  
> **username_2**: You could also consider the less technical notion of counting the number of edges that have to removed from the underlying undirected graph of the DAG, in order to turn that into a tree.  
> **username_3**: DAGs and trees are not close together. There are many problems which are hard on DAGs and easy on trees (more generally they are easy on class of digraps where their underlying undirected graph is of bounded treewidth).  
> **username_0**: @ChandraChekuri  But the problem I am considering is on a DAG. The DAG width for DAG would be 1. So DAG width isn’t of much relevance to the problem, apparently.  

---

## 0 answers

