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&amp\;
 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