Dynamic Parameterized Problems and Algorithms
Dynamic Parameterized Problems and Algorithms
复制标题
DOI：
10.1145/3395037
复制
发表时间：
2020-09-01
影响因子：
1.3
通讯作者：
Williams, Virginia Vassilevska
中科院分区：
文献类型：
--
作者：
Alman, Josh;Mnich, Matthias;Williams, Virginia Vassilevska
固定参数算法和核化算法是解决NP难问题的两种有效方法。然而，到目前为止，这些算法在很大程度上仅限于静态输入。在这篇文章中，我们为具有动态输入的基本NP难问题提供了固定参数算法和核化。我们考虑各种参数化图和命中集问题，已知有f（k）n（1+o（1））时间算法的输入大小为n，我们考虑的问题，是否有一个数据结构，支持小更新（如边/顶点/集/元素插入和删除）的更新时间。（k）n（o（1））;这样的更新时间基本上是最优的。更新和查询时间独立于n是特别理想的。在许多其他的结果，我们表明，反馈顶点集和k-PATH承认动态算法与f（k）log（O（1））n更新和查询时间的一些功能f取决于解决方案的大小k只。我们补充我们的积极成果，由几个条件和无条件的下限。例如，我们表明，与它们的无向对应物不同，有向反馈顶点集和有向k路径不允许具有n（o（1））更新和查询时间的动态算法，即使对于恒定的解大小k也是如此
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 article, 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 that 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.(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