News and events archive

Informatics colloquium 3. 10. 2017, 14:00 lecture hall D2 Mgr. Jan Obdržálek, Ph.D., FI MU Digraph Width Measures Abstract: Treewidth, defined by Robertson and Seymour, proved to be an extremely successful graph parameter. Intuitively, it measures how much tree-like a given graph is. Many problems which are NP-hard on general graphs become tractable on graphs of low treewidth. However treewidth quickly hits its limits once we try to apply it to directed graphs. Directed acyclic graphs (DAGs), on which many problems have simple efficient algorithms, can have arbitrarily high treewidth. Naturally one can ask whether there is a digraph width measure with all the nice properties of treewidth. In this talk we first quickly survey some of the known digraph width measures, and then try to answer the question whether there indeed is a good directed counterpart to treewidth.