2026-07-22T08:36:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10685 2024-03-06T10:46:27Z ddc:004 open_access

Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number (Track B: Automata, Logic, Semantics, and Theory of Programming) Casel, Katrin Day, Joel D. Fleischmann, Pamela Kociumaka, Tomasz Manea, Florin Schmid, Markus L. Graph and String Parameters NP-Completeness Approximation Algorithms We investigate the locality number, a recently introduced structural parameter for strings (with applications in pattern matching with variables), and its connection to two important graph-parameters, cutwidth and pathwidth. These connections allow us to show that computing the locality number is NP-hard but fixed-parameter tractable (when the locality number or the alphabet size is treated as a parameter), and can be approximated with ratio O(sqrt{log{opt}} log n). As a by-product, we also relate cutwidth via the locality number to pathwidth, which is of independent interest, since it improves the best currently known approximation algorithm for cutwidth. In addition to these main results, we also consider the possibility of greedy-based approximation algorithms for the locality number. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Katrin Casel and Joel D. Day and Pamela Fleischmann and Tomasz Kociumaka and Florin Manea and Markus L. Schmid 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.109 urn:nbn:de:0030-drops-106858 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.109 eng https://creativecommons.org/licenses/by/3.0/legalcode