Spined Categories: generalising tree-width beyond graphs

Add to your list(s) Download to your calendar using vCal

• Benjamin Bumpus, Glasgow
• Tuesday 23 March 2021, 14:00-15:00
• https://bham-ac-uk.zoom.us/j/88433307389.

If you have a question about this talk, please contact Johannes Carmesin.

Problems that are NP-hard in general are often tractable on inputs that have a recursive structure. For instance consider classes defined in terms of `graph decompositions’ such as of bounded tree- or clique-width graphs. Given the algorithmic success of graph decompositions, it is natural to seek analogues of these notions in other settings. What should a `tree-width-k’ digraph or lattice or temporal graph even look like? Since most decomposition notions are defined in terms of the internal structure of the decomposed object, generalizing a given notion of decomposition to a larger class of objects tends to be an arduous task. In this talk I will show how this difficulty can be reduced significantly by finding a characteristic property formulated purely in terms of the category that the decomposed objects inhabit, which defines the decomposition independently of the internal structure. I will introduce an abstract characterisation of tree-width as a vast generalisation of Halin’s definition of tree-width as the maximal graph parameter sharing certain properties with the Hadwiger number and chromatic number. Our uniform construction of tree-width provides a roadmap to the discovery of new tree-width-like parameters simply by collecting the relevant objects into our new notion of a spined category. This is joint work with Zoltan A. Kocsis (University of New South Wales).

This talk is part of the Study group in Graph Theory, Topology and Algorithms series.

This talk is included in these lists:

• https://bham-ac-uk.zoom.us/j/88433307389

Note that ex-directory lists are not shown.