Directed Graphs of Entanglement Two
Erich Gradel, Lukasz Kaiser and Roman Rabinovich
Abstract
Entanglement is a complexity measure for directed graphs that was used
to show that the variable hierarchy of the propositional modal
mu-calculus is strict. While graphs of entanglement zero and one are
indeed very simple, some graphs of entanglement two already contain
interesting nesting of cycles. This motivates our study of the class of
graphs of entanglement two, as these are both simple in a sense and
already complex enough for modelling certain structured systems.
Undirected graphs of entanglement two were already studied by Belkhir
and Santocanale and a structural decomposition for such graphs was
given. We study the general case of directed graphs of entanglement two
and prove that they can be decomposed as well, in a way similar to the
known decompositions for tree-width, DAG-width and Kelly-width.
Moreover, we show that all graphs of entanglement two have both
DAG-width and Kelly-width three. Since there exist both graphs with
DAG-width three and graphs with Kelly-width three, but with arbitrary
high entanglement, this confirms that graphs of entanglement two are a
very basic class of graphs with cycles intertwined in an interesting
way.