Campus Event Calendar

Event Entry

What and Who

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

Daniel Vaz
Max-Planck-Institut für Informatik - D1
AG 1, AG 3, AG 4, RG1, MMCI, AG 2, INET, AG 5, SWS  
Public Audience

Date, Time and Location

Tuesday, 8 December 2020
60 Minutes
Virtual talk
Virtual talk


In this talk, we will present new approximation results for the group

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.


Ben Wiederhake
+49 681 9325 1029
--email hidden
passcode not visible
logged in users only

Ben Wiederhake, 12/03/2020 16:07 -- Created document.