Structured Decompositions: Structural and Algorithmic Compositionality
From MaRDI portal
Publication:6404822
arXiv2207.06091MaRDI QIDQ6404822FDOQ6404822
Authors: Benjamin Merlin Bumpus, Zoltan A. Kocsis, Jade Master 
Publication date: 13 July 2022
Abstract: We introduce structured decompositions: category-theoretic generalizations of many combinatorial invariants -- including tree-width, layered tree-width, co-tree-width and graph decomposition width -- which have played a central role in the study of structural and algorithmic compositionality in both graph theory and parameterized complexity. Structured decompositions allow us to generalize combinatorial invariants to new settings (for example decompositions of matroids) in which they describe algorithmically useful structural compositionality. As an application of our theory we prove an algorithmic meta theorem for the Sub_P-composition problem which, when instantiated in the category of graphs, yields compositional algorithms for NP-hard problems such as: Maximum Bipartite Subgraph, Maximum Planar Subgraph and Longest Path.
Has companion code repository: https://github.com/algebraicjulia/structureddecompositions.jl
Analysis of algorithms (68W40) Structural characterization of families of graphs (05C75) Categories of spans/cospans, relations, or partial maps (18B10)
This page was built for publication: Structured Decompositions: Structural and Algorithmic Compositionality
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6404822)
