기초과학연구원 이산수학그룹
On May 21, 2021, Benjamin Bumpus from the University of Glasgow gave an online talk at the Virtual Discrete Math Colloquium about the directed branch-width for directed graphs. The title of his talk was “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.