Spined Categories: generalising tree-width beyond graphs.

Speaker: Benjamin Merlin Bumpus

Abstract: 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.)

Date and time: 21/10/2021 at 14:30 (Paris time)

Link to the talk: https://bbb-temp.grenet.fr/b/lou-9x7-69p