Approximation Algorithms for Network Design and Cut Problems in Bounded-Treewidth

Steiner tree problem on bounded-treewidth graphs. In the group Steiner
tree problem, the input is a graph together with sets of vertices called
groups; the goal is to choose one representative vertex from each group
and connect all the representatives with minimum cost. The problem is
hard to approximate even when the input graph is a tree: it is unlikely
that an approximation factor better than O(log^2 n) exists, and current
techniques cannot achieve this ratio even on graphs with treewidth 2. We
show an O(log^2 n)-approximation algorithm for bounded-treewidth graphs,
which matches the known lower bound for trees, and improves upon
previous techniques. These results imply new approximation algorithms
for other related problems, such as a high-connectivity extension of
group Steiner tree.

We will also introduce the firefighter problem, which models the spread
of fire in a graph, and briefly discuss our results for this problem on
trees and bounded-treewidth graphs.