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