Monoidal Width: Unifying Tree Width, Path Width and Branch Width

2022/02/15 by Elena Di Lavore, Di Lavore, Elena, Paweł Sobociński +1
Computer Science · #Category Theory (math.CT) #FOS: Computer and information sciences #FOS: Mathematics #Logic in Computer Science (cs.LO) #Logic, programming, and type systems #Model-Driven Software Engineering Techniques #Software Engineering Research

paper · pdf · doi:10.48550/arxiv.2202.07582

openalex publication_date 2022/02/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We introduce monoidal width as a measure of the difficulty of decomposing morphisms in monoidal categories. For graphs, we show that monoidal width and two variations capture existing notions, namely branch width, tree width and path width. We propose that monoidal width: (i) is a promising concept that, while capturing known measures, can similarly be instantiated in other settings, avoiding the need for ad-hoc domain-specific definitions and (ii) comes with a general, formal algebraic notion of decomposition using the language of monoidal categories.

Related

• Spined categories: generalizing tree-width beyond graphs
• Treewidth, Pathwidth and Cospan Decompositions
• On objects dual to tree-cut decompositions
• Line-width and path-width
• The Behavior of Tree-Width and Path-Width under Graph Operations and Graph Transformations