BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: In the Steiner Tree problem\, a set of terminal vertices in an
edge-weighted graph needs to be connected in the cheapest possible way. Th
is problem has been extensively studied from the viewpoint of approximation
and also parametrization. In particular\, on the one hand\, Steiner Tree i
s known to be APX-hard\, and on the other hand\, it is W[2]-hard if paramet
erized by the number of non-terminals (Steiner vertices) in the optimum sol
ution. In contrast to this\, we give an efficient parameterized approximati
on scheme (EPAS)\, which circumvents both hardness results. Moreover\, our
methods imply the existence of a polynomial size approximate kernelization
scheme (PSAKS) for the considered parameter. In the Directed Steiner Netw
ork problem we are given an arc-weighted digraph G \, a set of terminals
T \, and an (unweighted) directed request graph R with V(R) = T . Our ta
sk is to output a subgraph H of G of the minimum cost such that there i
s a directed path from s to t in H for all arcs st of R . It is kn
own that the problem can be solved in time |V(G)| O(|A(R)|) [Feldman&\;
Ruhl\, SIAM J. Comput. 2006] and cannot be solved in time |V(G)| o(|A(R)|)
even if G is planar\, unless Exponential-Time Hypothesis (ETH) fails [Chit
nis et al.\, SODA 2014]. However\, the reduction (and other reductions show
ing hardness of the problem) only shows that the problem cannot be solved i
n time |V(G)| o(|T|) \, unless ETH fails. Therefore\, there is a significan
t gap in the complexity with respect to |T| in the exponent. We show that D
irected Steiner Network is solvable in time f(|T|) · |V(G)| O( c g · |T|)
\, where c g is a constant depending solely on the genus g of G and
f is a computable function.
DTSTAMP:20180527T083300
DTSTART:20180528T160000
CLASS:PUBLIC
LOCATION:Technische Universität Berlin\n Institut für Mathematik\n Straße d
es 17. Juni 136\n 10623 Berlin\n room MA 041 (ground floor)
SEQUENCE:0
SUMMARY:Dušan Knop (University of Bergen): Parameterized Complexity of Stei
ner Problems
UID:89311645@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20180528-C2-Knop.html
END:VEVENT
END:VCALENDAR