From Edge Decomposition Formulae to Composition Algorithms

For some graph invariants simple decomposition formulae are known. Unfortunately, a straight forward implementation of such formulae usually leads to algorithms exponential in the number of edges or nodes of the graph even if the graph has a structure that wouldallow polynomial algorithms. This paper describes a way to derive polynomial algorithms for graphs of bounded pathwidth from edge decomposition formulae by using a variant of the composition method originally proposed by the author for the computation of graph invariants in graphs of small bandwidth.