Dynamic parameterized problems and algorithms

DOI10.4230/LIPICS.ICALP.2017.41MaRDI QIDQ5111372zbMATH OpenOpenAlexFDO

Authors Josh Alman, Matthias Mnich, Virginia Vassilevska Williams

Publication date 27 May 2020

Full work available at URL https://arxiv.org/abs/1707.00362

zbMATH Keywords

dynamic algorithmsfixed-parameter algorithms

Mathematics Subject Classification ID

Parameterized complexity, tractability and kernelization (68Q27) Analysis of algorithms (68W40)

Abstract: Fixed-parameter algorithms and kernelization are two powerful methods to solve $mathsfNP$-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 $mathsfNP$-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)lo{g}^{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 $kleq3$, 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$.

Recommendations

• Fast dynamic graph algorithms for parameterized problems
• Dynamic parameterized problems
• Dynamic Parameterized Problems
• On the parameterized complexity of dynamic problems
• Algorithms and Data Structures

Cited in

(15)

• Dynamic data structures for timed automata acceptance
• Dynamic kernels for hitting sets and set packing
• Linear-time parameterized algorithms with limited local resources
• Multistage vertex cover
• Reoptimization of parameterized problems
• Fast dynamic graph algorithms for parameterized problems
• Parameterized dynamic variants of red-blue dominating set
• Dynamic Parameterized Problems
• Dynamic Parameterized Problems and Algorithms
• How fast can we play Tetris greedily with rectangular pieces?
• Nearly time-optimal kernelization algorithms for the line-cover problem with big data
• Conditional lower bounds for dynamic geometric measure problems
• Conditional lower bounds for dynamic geometric measure problems
• Dynamic coloring of unit interval graphs with limited recourse budget
• Dynamic parameterized problems

This page was built for publication: Dynamic parameterized problems and algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111372)