Monoidal Width: Capturing Rank Width

DOI10.4204/EPTCS.380.16MaRDI QIDQ6150162zbMATH OpenFDO

Authors Elena di Lavore, Paweł Sobociński

Publication date 5 March 2024

Published in Electronic Proceedings in Theoretical Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Computer science (68-XX)

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.

Recommendations

• Monoidal Width
• Towards compositional graph theory
• Graph Operations Characterizing Rank-Width and Balanced Graph Expressions
• Graph operations characterizing rank-width
• Rank-width: algorithmic and structural results

Cites work

• scientific article; zbMATH DE number 2125662 (Why is no real title available?)
• A survey of graphical languages for monoidal categories
• A synthetic approach to Markov kernels, conditional independence and theorems on sufficient statistics
• A well-quasi-order for tournaments
• An algebraic theory of graph reduction
• Approximating clique-width and branch-width
• Categorical algebra
• Compositional game theory
• Diagrammatic Semantics for Digital Circuits.
• Disintegration and Bayesian inversion via string diagrams
• Full Rank Factorization of Matrices
• Graph complexity
• Graph expressions and graph rewritings
• Graph minors. I. Excluding a forest
• Graph minors. II. Algorithmic aspects of tree-width
• Graph minors. X: Obstructions to tree-decomposition
• On non-serial dynamic programming
• Optimal Linear Ordering
• Picturing quantum processes. A first course in quantum theory and diagrammatic reasoning
• S-functions for graphs
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The geometry of tensor calculus. I
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Towards compositional graph theory
• Upper bounds to the clique width of graphs

This page was built for publication: Monoidal Width: Capturing Rank Width

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