Alman, JoshJoshAlmanMnich, MatthiasMatthiasMnichVassilevska Williams, VirginiaVirginiaVassilevska Williams2020-01-282020-01-282017-0744th International Colloquium on Automata, Languages, and Programming (ICALP 2017)http://hdl.handle.net/11420/4608Fixed-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¹⁺ᵒ⁽¹⁾ 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ᵒ⁽¹⁾; 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)ᴼ⁽¹⁾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ᵒ⁽¹⁾ 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.enComputer Science - Data Structures and AlgorithmsComputer Science - Data Structures and AlgorithmsComputer Science - Computational ComplexityConference Paper10.4230/LIPIcs.ICALP.2017.411707.00362v1Other