论文标题
使用外部代数
Parameterized Sensitivity Oracles and Dynamic Algorithms using Exterior Algebras
论文作者
论文摘要
我们为各种参数化问题设计了第一个有效的灵敏度甲骨文和动态算法。我们的主要方法是从静态参数化算法设计中修改代数编码技术，该技术以前在动态上下文中尚未使用。我们特别建立在品牌，戴尔和Husfeldt [stoc'18]的“伸肌编码”方法上，该方法采用了外部代数的属性在不同领域。 对于有向图的$ K $ - Path检测问题，众所周知，不存在有效的动态算法（在细粒复杂性的流行假设下）。我们通过设计有效的敏感性甲骨文来阐明这一点，该甲骨文在$ 2^k poly（k）n^{ω+o（1）} $ time上预处理$ n $ pertices上的有针图高概率，是否包含长度$ k $的路径。我们还提供了确定性的敏感性Oracle，需要$ 4^k poly（k）n^{ω + o（1）} $预处理时间和$ \ ell^2 2^{ωk + o（k）} $ query时间，并获得随机敏感性的时间，并获得大约计算$ k $ paths的数量的任务。对于$ k $ - Path在无向图中的检测，我们获得了一个随机灵敏度甲骨文，带有$ O（1.66^k n^3）$预处理时间和$ o（\ ell^3 1.66^k）$查询时间，并且可以更好地绑定到无方向的biptite图。 此外，我们还提出了各种问题的第一种完全动态的算法：$ k $ - $ M $ - set $ k $ - 包装，$ t $ dominating set，$ d $ d $ d $二维$ k $ - 零件和$ k $ $ $ - $ - $ - 优等封面。例如，对于$ k $ - 各个封面，我们显示了一种随机动态算法，带有$ 2^k poly（k）polylog（n）$更新时间，以及带有$ 4^kpoly（k）polygog（n）$更新时间的确定性动态算法。
We design the first efficient sensitivity oracles and dynamic algorithms for a variety of parameterized problems. Our main approach is to modify the algebraic coding technique from static parameterized algorithm design, which had not previously been used in a dynamic context. We particularly build off of the `extensor coding' method of Brand, Dell and Husfeldt [STOC'18], employing properties of the exterior algebra over different fields. For the $k$-Path detection problem for directed graphs, it is known that no efficient dynamic algorithm exists (under popular assumptions from fine-grained complexity). We circumvent this by designing an efficient sensitivity oracle, which preprocesses a directed graph on $n$ vertices in $2^k poly(k) n^{ω+o(1)}$ time, such that, given $\ell$ updates (mixing edge insertions and deletions, and vertex deletions) to that input graph, it can decide in time $\ell^2 2^kpoly(k)$ and with high probability, whether the updated graph contains a path of length $k$. We also give a deterministic sensitivity oracle requiring $4^k poly(k) n^{ω+o(1)}$ preprocessing time and $\ell^2 2^{ωk + o(k)}$ query time, and obtain a randomized sensitivity oracle for the task of approximately counting the number of $k$-paths. For $k$-Path detection in undirected graphs, we obtain a randomized sensitivity oracle with $O(1.66^k n^3)$ preprocessing time and $O(\ell^3 1.66^k)$ query time, and a better bound for undirected bipartite graphs. In addition, we present the first fully dynamic algorithms for a variety of problems: $k$-Partial Cover, $m$-Set $k$-Packing, $t$-Dominating Set, $d$-Dimensional $k$-Matching, and Exact $k$-Partial Cover. For example, for $k$-Partial Cover we show a randomized dynamic algorithm with $2^k poly(k)polylog(n)$ update time, and a deterministic dynamic algorithm with $4^kpoly(k)polylog(n)$ update time.
