2
$\begingroup$

Tree decompositions and 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 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.

$\endgroup$
  • $\begingroup$ Seems similar to my question cstheory.stackexchange.com/questions/20449/… $\endgroup$ – seteropere Nov 16 '15 at 21:06
  • $\begingroup$ 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? $\endgroup$ – Fasermaler Nov 18 '15 at 7:42
  • $\begingroup$ 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. $\endgroup$ – Saeed Nov 18 '15 at 8:25
  • $\begingroup$ @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. $\endgroup$ – a3nm Nov 22 '15 at 14:52
  • $\begingroup$ @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. $\endgroup$ – a3nm Nov 22 '15 at 14:52

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.