Counting Minimum Cost Bounded Degree Subtrees in Graphs with Small 2-Vertex-Connected Components

Abstract

In this paper we present new algorithms for counting minimum cost bounded degree subtrees in connected graphs in which the 2-vertex-connected (biconnected) components have small sizes. The 2-vertex-connected components and the cut vertices can be organized into a block-cut vertex tree which is also a tree decomposition with small width of the graph. We present a dynamic programming algorithm which is very efficient on this particular tree decomposition and we also discuss methods of solving the problem given an arbitrary tree decomposition with small width. Among some of the most important results is an algorithm which can efficiently compute the number of subtrees of a (small) graph corresponding to each possible degree sequence.