2026-07-21T19:27:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7441 2024-03-06T10:40:20Z ddc:004 open_access

Dynamic Parameterized Problems and Algorithms Alman, Josh Mnich, Matthias Vassilevska Williams, Virginia Dynamic algorithms fixed-parameter algorithms Fixed-parameter algorithms and kernelization are two powerful methods to solve NP-hard problems. Yet, so far those algorithms have been largely restricted to static inputs. In this paper we provide fixed-parameter algorithms and kernelizations for fundamental NP-hard problems with dynamic inputs. We consider a variety of parameterized graph and hitting set problems which are known to have f(k)n^{1+o(1)} time algorithms on inputs of size n, and we consider the question of whether there is a data structure that supports small updates (such as edge/vertex/set/element insertions and deletions) with an update time of g(k)n^{o(1)}; such an update time would be essentially optimal. Update and query times independent of n are particularly desirable. Among many other results, we show that Feedback Vertex Set and k-Path admit dynamic algorithms with f(k)log O(1) n update and query times for some function f depending on the solution size k only. We complement our positive results by several conditional and unconditional lower bounds. For example, we show that unlike their undirected counterparts, Directed Feedback Vertex Set and Directed k-Path do not admit dynamic algorithms with n^{o(1) } update and query times even for constant solution sizes k <= 3, assuming popular hardness hypotheses. We also show that unconditionally, in the cell probe model, Directed Feedback Vertex Set cannot be solved with update time that is purely a function of k. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Josh Alman and Matthias Mnich and Virginia Vassilevska Williams 2017 Is Part Of LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2017.41 urn:nbn:de:0030-drops-74419 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.41 eng https://creativecommons.org/licenses/by/3.0/legalcode