Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Beyond Metric Embedding: Approximating Group Steiner Trees on Bounded Treewidth Graphs
Speaker:Daniel Vaz
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 5 January 2017
Duration:30 Minutes
Building:E1 4 - MPI-INF

The Group Steiner Tree (GST) problem is a classical problem in combinatorial optimization and theoretical computer science. In the Edge-Weighted Group Steiner Tree (EW-GST) problem, we are given an undirected graph G=(V,E) on n vertices with edge costs c, a source vertex s and a collection of subsets of vertices, called groups, S_1, ..., S_k (subsets of V). The goal is to find a minimum-cost tree H that connects s to some vertex from each group S_i, for all i = 1, 2, ..., k. The Node-Weighted Group Steiner Tree (NW-GST) problem has the same setting, but the costs are associated with nodes. The goal is to find a minimum-cost node set X such that G[X] connects every group to the source.

When G is a tree, both EW-GST and NW-GST admit a polynomial-time O(\log n \log k) approximation algorithm due to the seminal result of [Garg et al. SODA'98 / J.Algorithm]. The matching hardness of (\log^{2-\epsilon} n) is known even for tree instances of EW-GST and NW-GST [Halperin and Krauthgamer STOC'03]. In general graphs, all polynomial-time approximation algorithms reduce the problem to a tree instance using the metric-tree embedding, incurring a loss of O(\log n) on the approximation factor [Bartal, FOCS'96; Fakcharoenphol et al., FOCS'03 / JCSS]. This yields an approximation ratio of O(\log^2 n \log k) for EW-GST. Using metric-tree embedding, this factor cannot be improved: The loss of \Omega(\log n) is necessary on some input graphs (e.g. grids and expanders). There are alternative approaches that avoid metric-tree embedding, e.g., the algorithm of [Chekuri and Pal, FOCS'05], which gives a tight approximation ratio, but none of which achieves polylogarithmic approximation in polynomial-time. This state of the art shows a clear lack of understanding of GST in general graphs beyond the metric-tree embedding technique. For NW-GST (for which the metric-tree embedding does not apply), not even a polynomial-time polylogarithmic approximation algorithm is known.

In this paper, we present O(\log n \log k) approximation algorithms that run in time n^{O(tw(G)^2)} for both NW-GST and EW-GST, where tw(G)denotes the treewidth of graph G. The key to both results is a different type of "tree-embedding" that produces a tree of much bigger size, but does not cause any loss on the approximation factor. Our embedding is inspired by dynamic programming, a technique which is typically not applicable to group connectivity problems.

Name(s):Daniel Vaz
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Created by:Daniel Vaz, 11/29/2016 03:28 PMLast modified by:Uwe Brahm/MPII/DE, 01/05/2017 04:01 AM
  • Daniel Vaz, 12/01/2016 02:03 PM
  • Daniel Vaz, 11/29/2016 03:28 PM -- Created document.