BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:5323ba87-14e2-47d3-837e-11e824f5cc47
X-WR-CALNAME:GT algodist - Kernelizing Temporal Exploration Problems\, Petr
 a Wolf
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20251026T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20231029T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20241027T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20230326T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20240331T020000
RDATE:20250330T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:5323ba87-14e2-47d3-837e-11e824f5cc47
DTSTAMP:20260510T232132Z
CLASS:PUBLIC
DESCRIPTION:Petra Wolf\, «Kernelizing Temporal Exploration Problems»\n\nAbs
 tract:\n\nWe study the kernelization of exploration problems on temporal g
 raphs. A temporal graph consists of a finite sequence of snapshot graphs G
  = (G1\, G2\, …\, GL) that share a common vertex set but might have differ
 ent edge sets. The non-strict temporal exploration problem (NS-TEXP for sh
 ort) introduced by Erlebach and Spooner\, asks if a single agent can visit
  all vertices of a given temporal graph where the edges traversed by the a
 gent are present in non-strict monotonous time steps\, i.e.\, the agent ca
 n move along the edges of a snapshot graph with infinite speed.  The explo
 ration must at the latest be completed in the last snapshot graph. The opt
 imization variant of this problem is the k-arb NS-TEXP problem\, where the
  agent’s task is to visit at least k vertices of the temporal graph. We sh
 ow that under standard computational complexity assumptions\, neither of t
 he problems NS-TEXP nor k-arb NS-TEXP allow for polynomial kernels in the 
 standard parameters: number of vertices n\, lifetime L\, number of vertice
 s to visit k\, and maximal number of connected components per time step γ\
 ; as well as in the combined parameters L + k\, L + γ\, and k + γ. On the 
 way to establishing these lower bounds\, we answer a couple of questions l
 eft open by Erlebach and Spooner. We also initiate the study of structural
  kernelization by identifying a new parameter of a temporal graph Informal
 ly\, this parameter measures how dynamic thetemporal graph is. Our main al
 gorithmic result is the construction of a polynomial (in p(G)) kernel for 
 the more general Weighted k-arb NS-TEXP problem\, where weights are assign
 ed to the vertices and the task is to find a temporal walk of weight at le
 ast k.\n\n\n\nhttps://algodist.labri.fr/index.php/Main/GT
DTSTART;TZID=Europe/Paris:20231206T110000
DTEND;TZID=Europe/Paris:20231206T120000
LOCATION:LaBRI salle 178 - lien visio https://webconf.u-bordeaux.fr/b/arn-4
 tr-7gp
SEQUENCE:0
SUMMARY:GT algodist - Kernelizing Temporal Exploration Problems\, Petra Wol
 f
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
