Informatické kolokvium 3. 10. Digraph Width Measures
Informatické kolokvium 3. 10. 2017, 14:00 posluchárna D2
Mgr. Jan Obdržálek, Ph.D., FI MU
Digraph Width Measures
Abstrakt: 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.