Spined categories: generalizing tree-width beyond graphs

DOI10.1016/J.EJC.2023.103794MaRDI QIDQ6056559zbMATH OpenOpenAlexFDO

Authors Benjamin Merlin Bumpus, Zoltan A. Kocsis

Publication date 2 October 2023

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2104.01841

zbMATH Keywords

computational problems on graphstree-width-like invariants

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Categorical structures (18D99)

Abstract: Tree-width is an invaluable tool for computational problems on graphs. But often one would like to compute on other kinds of objects (e.g. decorated graphs or even algebraic structures) where there is no known tree-width analogue. Here we define an abstract analogue of tree-width which provides a uniform definition of various tree-width-like invariants including graph tree-width, hypergraph tree-width, complemented tree-width and even new constructions such as the tree-width of modular quotients. We obtain this generalization by developing a general theory of categories that admit abstract analogues of both tree decompositions and tree-width; we call these pseudo-chordal completions and the triangulation functor respectively.

Recommendations

• Tree-decompositions of small pathwidth
• scientific article; zbMATH DE number 772777
• From tree-decompositions to clique-width terms
• Width functions for hypertree decompositions
• A Natural Generalization of Bounded Tree-Width and Bounded Clique-Width

Cites work

• F-rank-width of (edge-colored) graphs
• A Combinatorial Decomposition Theory
• A survey of the algorithmic aspects of modular decomposition
• Approximating clique-width and branch-width
• Codensity and the ultrafilter monad
• Digraph measures: Kelly decompositions, games, and orderings
• Digraphs of bounded width
• Directed tree-width
• Foundations of Software Science and Computation Structures
• Graph minors. II. Algorithmic aspects of tree-width
• Graph minors. X: Obstructions to tree-decomposition
• Graph minors. XX: Wagner's conjecture
• Graph theory
• Handle-rewriting hypergraph grammars
• scientific article; zbMATH DE number 5761737 (Why is no real title available?)
• Hypertree width and related hypergraph invariants
• Layered separators in minor-closed graph classes with applications
• Mathematical Foundations of Computer Science 2005
• Nonserial dynamic programming
• On miniaturized problems in parameterized complexity theory
• Parameterized algorithms
• Partitive hypergraphs
• S-functions for graphs
• The dag-width of directed graphs
• The monadic second-order logic of graphs. X: Linear orderings
• The NP-completeness column: an ongoing guide
• The structure of graphs not admitting a fixed immersion

Cited in

(1)

• Monoidal Width

This page was built for publication: Spined categories: generalizing tree-width beyond graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6056559)