Computing the Invariant Polynomials of Graphs, Networks and Matroids

Hiroshi IMAI  

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

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

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.