Computing the Invariant Polynomials of Graphs, Networks and Matroids

Hiroshi IMAI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E83-D   No.3   pp.330-343
Publication Date: 2000/03/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: INVITED SURVEY PAPER
Category: Algorithms for Matroids and Related Discrete Systems
Keyword: 
Tutte polynomial,  matroid,  simplicial complex,  network reliability,  BDD,  

Full Text: PDF(513.5KB)>>
Buy this Article




Summary: 
The invariant polynomials of discrete systems such as graphs, matroids, hyperplane arrangements, and simplicial complexes, have been theoretically investigated actively in recent years. These invariants include the Tutte polynomial of a graph and a matroid, the chromatic polynomial of a graph, the network reliability of a network, the Jones polynomial of a link, the percolation function of a grid, etc. The computational complexity issues of computing these invariants have been studied and most of them are shown to be #P-complete. But, these complexity results do not imply that we cannot compute the invariants of a given instance of moderate size in practice. To meet large demand of computing these invariants in practice, there have been proposed a framework of computing the invariants by using the binary decision diagrams (BDD for short). This provides mildly exponential algorithms which are useful to solve moderate-size practical problems. This paper surveys the BDD-based approach to computing the invariants, together with some computational results showing the usefulness of the framework.