Kolloquiumsvortrag, Syamantak Das, Universität Bremen / am 14.07.2017

14.07.2017 von 14:15 bis 15:45

Ludewig-Meyn-Str. 2, Raum Ü2/K (LMSe, R. Ü2/K)

Beyond Metric Embedding : Approximating the Group Steiner Tree on Bounded Treewidth Graphs

We consider the  fundamental problem of finding the minimum cost Group Steiner Tree (GST) on bounded treewidth graphs. In GST, we are given an edge-(or node-)weighted graph $G$ on $n$ nodes with treewidth $w$, a root node $r$ and a collection of groups $S_i$ which are subsets of the vertex set. The goal is to find a minimum-cost subgraph $H$ that connects the root node to every group. This problem has been shown to be NP-hard to approximate within a factor of $\omega(log^(2-\epsilon) k)$ [Halperin and Krauthgamer, STOC 2002], where $k$ is the number of groups in the input instance. The best known approximation algorithm achieves a factor of $O(log^2 n log k)$ [Garg et al SODA 1998 and Fakcharoenphol et al. STOC 2003] and bridging this gap has been a long standing open question.

In the current work, we take a step towards answering this question by giving a polynomial time algorithm that has an approximation ratio of $O(log(n) log(k))$ for graphs of bounded treewidth. In particular, our algorithm runs in time $O(n^{w\log w})$. The key ingredient of all our algorithms is a construction of a tree sparsifier from the input graph that preserves rooted connectivity in any subgraph, which could be of independent interest.


Prof. Dr. Klaus Jansen

Diesen Termin meinem iCal-Kalender hinzufügen