<p><strong><a href="https://en.wikipedia.org/wiki/Tree_decomposition" rel="noreferrer">Tree decompositions</a></strong> and <a href="https://en.wikipedia.org/wiki/Treewidth" rel="noreferrer">treewidth</a> are a standard way to measure how close an <em>undirected</em> graph is to a tree. I am studying decompositions of <em>directed acyclic</em> graphs (DAGs), and have come to define them as follows:</p>

<p>Given a DAG $G = (V, E)$, letting $G'$ be the undirected graph obtained by forgetting about edge orientations, a <em>tree decomposition</em> of $G$ is a tree decomposition $T$ of $G'$ as a <em>rooted</em>, <em>directed</em> tree, such that for any bag $b \in T$ and any vertex $v$ of $V$ in $b$, if $v$ occurs in none of the children of $b$, then for any directed edge $(u, v) \in E$, we have $u \in b$. The <em>width</em> of $G$ under this definition is then, as usual, the minimum across all decompositions $T$ of the maximal cardinality of a bag in $T$ minus one.</p>

<p>My general question is: <strong>Is such a notion of tree decomposition of a DAG known?</strong></p>

<p>I know that there are existing definitions of tree decompositions for directed graphs, such as D-width, DAG-width, and directed treewidth. However, I don't think they are related to this definition, because, according to all of them, DAGs have low treewidth. Indeed, these definitions consider acyclic graphs as "simple". By contrast my definition only applies to DAGs, and its extension to general directed graphs is not interesting: unless I'm wrong, it implies that all elements of each strongly connected component must co-occur in a bag.</p>

<p>Further, in my case, the width of a DAG may be <em>more</em> than that of the corresponding undirected graph. In fact, a tree decomposition of a DAG $G$ in this sense is a standard tree decomposition of the <a href="https://en.wikipedia.org/wiki/Moral_graph" rel="noreferrer">moral graph</a> of $G$, with additional conditions enforcing it to have a certain "directed" shape. I think the treewidth of the DAG in this sense can still be arbitrarily larger than that of the moral graph, but I'm not sure how to characterize the DAGs that would have "bounded treewidth" in the sense I proposed.</p>

<p><strong>Motivation.</strong> In my context, the DAG is a circuit, and I use the tree decomposition to reason about valuations. The property that I require is designed to ensure the following: when processing the tree decomposition bottom-up, when we reach a new bag and we see a new element, we can examine its valuations based on that of its children, which are known because the children must be in the bag: we do not need to guess the valuation (as we would have to if it depended on nodes we haven't seen yet). I suspect that there may also be a relationship to inference in graphical models, where message passing needs to be done in only one direction, but I was unable to find references.</p>

CC BY-SA 3.0
2015-11-16T21:06:34.353Z
Seems similar to my question http://cstheory.stackexchange.com/questions/20449/how-to-go-from-a-dag-model-to-bounded-treewidth
seteropere
CC BY-SA 3.0
2015-11-18T07:42:05.970Z
This is more of a clarifying question for myself, but instead of a moralization it seems more natural to me to consider the strongly connected components of a DAG. Since a DAG is a directed forest by definition, it's strongly connected components would be directed trees which (ignoring directionality) would give you a decomposition with a nice small treewidth of 1. Is there any benefit you gain from the moralization that you don't get from this admittedly naïve decomposition strategy?
Fasermaler
CC BY-SA 3.0
2015-11-18T08:25:48.550Z
I don't understand what is exact definition of your DAG decomposition. But as far as I understand it seems ti be useless for dynamic programming purposes. e.g connect some directed stars as a chain. With your definition the corresponding DAG has a big width so we can't enumerate over all positions in a single bag, but in fact even without any decomposition knowledge many problems are solvable with DP in this particular digraph.
Saeed
CC BY-SA 3.0
2015-11-22T14:52:29.110Z
@Fasermaler: Your comment doesn't make sense to me: the SCCs of a DAG are all singletons, and the SCC graph is the DAG itself, it is not in general a directed forest.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2015-11-22T14:52:32.437Z
@Saeed: What is it that you don't understand in the definition? I am aware that for most dynamic programming purposes it suffices for the DAG to have bounded treewidth in the standard sense (i.e., forgetting about the orientation), but for the applications I have I mind, I need to impose conditions like the one I give in my definition.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2015-11-22T16:16:33.607Z
I cannot tell if this fits your need, but the following paper considers two digraph width measures, namely DAG-depth and K-width, which are are arbitrarily large on DAGs: http://www.fi.muni.cz/~hlineny/papers/kenny-full-v3-strip.pdf
Hermann Gruber
CC BY-SA 3.0
2015-11-23T13:12:16.223Z
You mixed somethings and missed somethings. First of all for digraphs (or even undir graphs) we don't say tree decomposition as a general term, we only say decomposition, it may be X or Y decomposition in particular. Second you did not define what is your decomposition width. I guess as usual a largest bag size from a decomposition with smallest largest bag among all valid decompositions.
Saeed
CC BY-SA 3.0
2015-11-23T13:12:51.600Z
Third the main point of my comment was to say that decomposition helps to solve bunch of problems easier. Not being a problem itself. That means for your particular problem you may get better result by careful analysis and algorithm design rather than trying generalized approach. Fourth, as best of my knowledge decomposition mentioned by you and completed by my comment, never have been studied.
Saeed
CC BY-SA 3.0
2015-11-23T15:10:35.777Z
@a3nm You're absolutely right, it doesn't make any sense to me either now that you've clarified it. Somehow I got stuck on this directed forest notion, so thanks for responding.
Fasermaler
CC BY-SA 3.0
2015-11-23T17:00:29.757Z
@Saeed: Indeed the definition of width was missing, it was as you inferred it, I added it. Thanks!
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2015-11-23T17:04:14.027Z
@HermannGruber: DAG-depth is not the same thing as a long directed path has arbitrarily high DAG-depth but constant width in my definition. The same applies to K-width because it is greater than or equal to the DAG-width minus one, so it is again unbounded on directed paths. Still, thanks for the suggestion!
Antoine Amarilli 'a3nm'
<reference-request><directed-acyclic-graph><treewidth>
Tree decomposition for DAGs
Antoine Amarilli 'a3nm'
# Tree decomposition for DAGs

(Asked by: username_0 on 2015-11-16)

**[Tree decompositions](https://en.wikipedia.org/wiki/Tree_decomposition)** and [treewidth](https://en.wikipedia.org/wiki/Treewidth) are a standard way to measure how close an *undirected* graph is to a tree. I am studying decompositions of *directed acyclic* graphs (DAGs), and have come to define them as follows:

Given a DAG $G = (V, E)$, letting $G'$ be the undirected graph obtained by forgetting about edge orientations, a *tree decomposition* of $G$ is a tree decomposition $T$ of $G'$ as a *rooted*, *directed* tree, such that for any bag $b \in T$ and any vertex $v$ of $V$ in $b$, if $v$ occurs in none of the children of $b$, then for any directed edge $(u, v) \in E$, we have $u \in b$. The *width* of $G$ under this definition is then, as usual, the minimum across all decompositions $T$ of the maximal cardinality of a bag in $T$ minus one.

My general question is: **Is such a notion of tree decomposition of a DAG known?**

I know that there are existing definitions of tree decompositions for directed graphs, such as D-width, DAG-width, and directed treewidth. However, I don't think they are related to this definition, because, according to all of them, DAGs have low treewidth. Indeed, these definitions consider acyclic graphs as "simple". By contrast my definition only applies to DAGs, and its extension to general directed graphs is not interesting: unless I'm wrong, it implies that all elements of each strongly connected component must co-occur in a bag.

Further, in my case, the width of a DAG may be *more* than that of the corresponding undirected graph. In fact, a tree decomposition of a DAG $G$ in this sense is a standard tree decomposition of the [moral graph](https://en.wikipedia.org/wiki/Moral_graph) of $G$, with additional conditions enforcing it to have a certain "directed" shape. I think the treewidth of the DAG in this sense can still be arbitrarily larger than that of the moral graph, but I'm not sure how to characterize the DAGs that would have "bounded treewidth" in the sense I proposed.

**Motivation.** In my context, the DAG is a circuit, and I use the tree decomposition to reason about valuations. The property that I require is designed to ensure the following: when processing the tree decomposition bottom-up, when we reach a new bag and we see a new element, we can examine its valuations based on that of its children, which are known because the children must be in the bag: we do not need to guess the valuation (as we would have to if it depended on nodes we haven't seen yet). I suspect that there may also be a relationship to inference in graphical models, where message passing needs to be done in only one direction, but I was unable to find references.

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

> **Comments:**
> **username_1**: Seems similar to my question http://cstheory.stackexchange.com/questions/20449/how-to-go-from-a-dag-model-to-bounded-treewidth  
> **username_2**: This is more of a clarifying question for myself, but instead of a moralization it seems more natural to me to consider the strongly connected components of a DAG. Since a DAG is a directed forest by definition, it's strongly connected components would be directed trees which (ignoring directionality) would give you a decomposition with a nice small treewidth of 1. Is there any benefit you gain from the moralization that you don't get from this admittedly naïve decomposition strategy?  
> **username_3**: I don't understand what is exact definition of your DAG decomposition. But as far as I understand it seems ti be useless for dynamic programming purposes. e.g connect some directed stars as a chain. With your definition the corresponding DAG has a big width so we can't enumerate over all positions in a single bag, but in fact even without any decomposition knowledge many problems are solvable with DP in this particular digraph.  
> **username_0**: @username_2: Your comment doesn't make sense to me: the SCCs of a DAG are all singletons, and the SCC graph is the DAG itself, it is not in general a directed forest.  
> **username_0**: @username_3: What is it that you don't understand in the definition? I am aware that for most dynamic programming purposes it suffices for the DAG to have bounded treewidth in the standard sense (i.e., forgetting about the orientation), but for the applications I have I mind, I need to impose conditions like the one I give in my definition.  
> **username_4**: I cannot tell if this fits your need, but the following paper considers two digraph width measures, namely DAG-depth and K-width, which are are arbitrarily large on DAGs: http://www.fi.muni.cz/~hlineny/papers/kenny-full-v3-strip.pdf  
> **username_3**: You mixed somethings and missed somethings. First of all for digraphs (or even undir graphs) we don't say tree decomposition as a general term, we only say decomposition, it may be X or Y decomposition in particular. Second you did not define what is your decomposition width. I guess as usual a largest bag size from a decomposition with smallest largest bag among all valid decompositions.  
> **username_3**: Third the main point of my comment was to say that decomposition helps to solve bunch of problems easier. Not being a problem itself. That means for your particular problem you may get better result by careful analysis and algorithm design rather than trying generalized approach. Fourth, as best of my knowledge decomposition mentioned by you and completed by my comment, never have been studied.  
> **username_2**: @a3nm You're absolutely right, it doesn't make any sense to me either now that you've clarified it. Somehow I got stuck on this directed forest notion, so thanks for responding.  
> **username_0**: @username_3: Indeed the definition of width was missing, it was as you inferred it, I added it. Thanks!  
> **username_0**: @HermannGruber: DAG-depth is not the same thing as a long directed path has arbitrarily high DAG-depth but constant width in my definition. The same applies to K-width because it is greater than or equal to the DAG-width minus one, so it is again unbounded on directed paths. Still, thanks for the suggestion!  

---

## 0 answers

