W内的不适应性：对Steiner定位的案例研究

作者：Michal Wlodarczyk

摘要：在k-Steiner方向问题中，我们给出了一个混合图，即有向和无向边，以及一组k个端子对。目标是找到无向边的方向，以最大化从源到水槽的路径的终端对的数量。当通过k参数化时，已知该问题为W [1] - 硬，并且对于假设Gap-ETH的FPT算法难以近似达到某个常数。另一方面，没有比O（k）更好的近似值。

假设W [1]≠FPT，我们证明k-Steiner方向不允许使用亚对数近似算法，即使参数化运行时间也是如此。为了获得这个结果，我们通过基于散列的间隙放大技术将问题简化为自身，即使在FPT范例之外也是如此。准确地说，在相同的假设下，我们排除了参数化算法的形式（logk）o（1）和纯多项式运行时间的（logn）o（1）的任何近似比。这构成了通过FPT理论的工具获得的多项式时间算法的新的不可近似性结果。此外，我们证明k-Steiner方向为W [1] - 完全，提供了在参数化复杂性类中完成的自然近似任务的示例。

最后，我们将我们的技术应用于Directed Multicut的最大化版本，并获得一个简单的证据，证明该问题不允许采用比率O（k12-ε）的FPT近似（假设W [1]≠FPT）并且没有多项式时间近似与比率O（m12-ε）（假设NP⊈co-RP）。

原文标题：Inapproximability within W[1]: the case of Steiner Orientation

原文摘要：

地址：https://arxiv.org/abs/1907.06529