Monoidal Width: Capturing Rank Width
arXiv:2205.08916 · doi:10.4204/EPTCS.380.16
Abstract
Monoidal width was recently introduced by the authors as a measure of the complexity of decomposing morphisms in monoidal categories. We have shown that in a monoidal category of cospans of graphs, monoidal width and its variants can be used to capture tree width, path width and branch width. In this paper we study monoidal width in a category of matrices, and in an extension to a different monoidal category of open graphs, where the connectivity information is handled with matrix algebra and graphs are composed along edges instead of vertices. We show that here monoidal width captures rank width: a measure of graph complexity that has received much attention in recent years.
arXiv commentIn Proceedings ACT 2022, arXiv:2307.15519
References in corpus (9)
- Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus
- A synthetic approach to Markov kernels, conditional independence and theorems on sufficient statistics
- Disintegration and Bayesian Inversion via String Diagrams
- The quantum FFT can be classically simulated
- Interacting Hopf Algebras: the theory of linear systems
- String Diagrammatic Electrical Circuit Theory
- A Graphical Calculus for Lagrangian Relations
- Monoidal Width: Unifying Tree Width, Path Width and Branch Width
- Spined categories: generalizing tree-width beyond graphs