Benjamin Bumpus, Directed branch-width: A directed analogue of tree-width

Many problems that are NP-hard in general become tractable on `structurally recursive’ graph classes. For example, consider classes of bounded tree- or clique-width. Since the 1990s, many directed analogues of tree-width have been proposed. However, many natural problems (e.g. directed HamiltonPath and MaxCut) remain intractable on such digraph classes of `bounded width’.

In this talk, I will introduce a new tree-width analogue for digraphs called directed branch-width which allows us to define digraph classes for which many problems (including directed HamiltonPath and MaxCut)  become linear-time solvable. Furthermore, via the definition of directed branch-width, I will obtain a generalisation to digraphs of Gurski and Wanke’s characterization of graph classes of bounded tree-width in terms of their line graphs.

This is joint work with Kitty Meeks and William Pettersson.