BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: We investigate the locality number\, a recently introduced str
 uctural parameter for strings (with applications in pattern matching with v
 ariables)\, and its connection to two important graph-parameters\, cutwidth
  and pathwidth. These connections allow us to show that computing the local
 ity number is NP-hard\, but fixed-parameter tractable\, if parameterised by
  the locality number or by the alphabet size\, which has been formulated as
  open problems in the literature. Moreover\, the locality number can be app
 roximated with ratio O(\sqrt{log(opt)} log(n))$.  An important aspect of ou
 r work --- that is relevant in its own right and of independent interest --
 - is that we identify connections between the string parameter of the local
 ity number on the one hand\, and the famous graph parameters of cutwidth an
 d pathwidth\, on the other hand. These two parameters have been jointly inv
 estigated in the literature (with respect to exact\, parameterised and appr
 oximation algorithms)\, and are arguably among the most central graph param
 eters that are based on "linearisations" of graphs. Most importantly\, we r
 elate cutwidth with pathwidth via the locality number\, which results in an
  approximation preserving reduction that improves the currently best known 
 approximation algorithm for cutwidth.  [This is based on joint work with Ka
 trin Casel\, Joel D. Day\, Pamela Fleischmann\, Tomasz Kociumaka\, and Flor
 in Manea\, published in Proc. ICALP'19.] 
DTSTAMP:20211207T223900
DTSTART:20211213T160000
CLASS:PUBLIC
LOCATION:Online via Zoom.
SEQUENCE:0
SUMMARY:Markus Schmid (Humboldt-Universität zu Berlin): Graph and String Pa
 rameters: Connections Between Pathwidth\, Cutwidth and the Locality Number
UID:107919915@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20211213-C-Schmid.html
END:VEVENT
END:VCALENDAR