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.

  • $\begingroup$ You may want to see also the paper on DAG width. sciencedirect.com/science/article/pii/S0095895612000329 $\endgroup$ – Chandra Chekuri Jun 22 '18 at 0:08
  • $\begingroup$ 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. $\endgroup$ – Bart Jansen Jun 22 '18 at 14:01
  • $\begingroup$ 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). $\endgroup$ – Saeed Jun 23 '18 at 0:06
  • $\begingroup$ @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. $\endgroup$ – am_rf24 Jul 9 '18 at 4:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.