Finiteness conditions for graph algebras over tropical semirings

MaRDI QIDQ4584114zbMATH OpenFDO

Authors Nadia Labai, Johann A. Makowsky

Publication date 29 August 2018

Full work available at URL https://arxiv.org/abs/1405.2547, http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAT0132

zbMATH Keywords

clique-widthHankel matricestree-widthgraph parametersgraph algebrasconnection matrics

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Analysis of algorithms and problem complexity (68Q25) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Abstract: Connection matrices for graph parameters with values in a field have been introduced by M. Freedman, L. Lov{'a}sz and A. Schrijver (2007). Graph parameters with connection matrices of finite rank can be computed in polynomial time on graph classes of bounded tree-width. We introduce join matrices, a generalization of connection matrices, and allow graph parameters to take values in the tropical rings (max-plus algebras) over the real numbers. We show that rank-finiteness of join matrices implies that these graph parameters can be computed in polynomial time on graph classes of bounded clique-width. In the case of graph parameters with values in arbitrary commutative semirings, this remains true for graph classes of bounded linear clique-width. B. Godlin, T. Kotek and J.A. Makowsky (2008) showed that definability of a graph parameter in Monadic Second Order Logic implies rank finiteness. We also show that there are uncountably many integer valued graph parameters with connection matrices or join matrices of fixed finite rank. This shows that rank finiteness is a much weaker assumption than any definability assumption.

Recommendations

• Connection Matrices for MSOL-Definable Structural Invariants
• Connection matrices and the definability of graph parameters
• Connection matrices and the definability of graph parameters
• Connection matrices
• Graph Operations Characterizing Rank-Width and Balanced Graph Expressions

Cited in

(5)

• Recurrence relations for graph polynomials on bi-iterative families of graphs
• scientific article; zbMATH DE number 7663171 (Why is no real title available?)
• Connection matrices and the definability of graph parameters
• Logics of finite Hankel rank
• Connection matrices and the definability of graph parameters

This page was built for publication: Finiteness conditions for graph algebras over tropical semirings

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