在有向几何集问题中，给定一个（有向）图，我们需要寻找一个小的解集 $S \subseteq V(G)$，使得每个顶点都位于 $S$ 中两个顶点之间的最短有向路径上。已知该问题在参数化解集大小 $k$ 时是 W[2]-困难的，即使是在有向无环图（DAG）中。
我们的第一个结果是针对一般有向图的有向几何集问题的一个核大小为 $2^{O(vcn)}$，其中 $vcn$ 表示底层（无向）图的顶点覆盖数。这意味着存在一个运行时间为 $2^{O(vcn^2)} \cdot n^{O(1)}$ 的算法。此外，我们证明，假设指数时间假设（ETH）成立，该问题不允许存在运行时间为 $2^{o(vcn^2)} \cdot n^{O(1)}$ 的算法。
接下来，我们展示在一般有向图中，有向几何集问题具有一个自然核，其大小为 $(k\Delta)^{O(rdiam)}$，其中 $\Delta$ 为最大度数，$rdiam$ 表示有向图的可达直径（无向图的直径的自然类比）。这导致一个运行时间为 $(k\Delta)^{O(rdiam \cdot k)} \cdot n^{O(1)}$ 的算法。我们进一步证明，假设 ETH 成立，该问题不允许存在运行时间为 $(k\Delta)^{o(rdiam \cdot k)} \cdot n^{O(1)}$ 的算法。
最后，我们通过以下难度结果证明了结合参数的必要性：
- 在最大度数为 3 的有向图中，针对 $k$ 的参数化是 W[2]-困难的。
- 针对最大度数和可达直径的参数化是 para-NP-困难的。
由 Araújo 和 Arraes [DAM 2022] 的结果可以推断，该问题在可达直径为 3 的图中仍然是 W[2]-困难的。我们的所有条件下界和难度结果即使在输入有向图限制为 DAG 时也依然成立。
博主点评： 本文深入探讨了有向几何集问题的结构参数化，揭示了该问题在不同参数化下的复杂性及其算法限制。通过系统的困难性证明，作者为未来的研究提供了重要的理论基础，尤其是在图论和算法设计领域的应用潜力值得关注。