论文标题
通过查找和击中奇数周期，点分离和障碍物清除
Point Separation and Obstacle Removal by Finding and Hitting Odd Cycles
论文作者
论文摘要
假设我们得到了一对$ s，t $和一套$ n $几何对象的$ s $ s $，称为障碍物。 We show that in polynomial time one can construct an auxiliary (multi-)graph $G$ with vertex set $S$ and every edge labeled from $\{0, 1\}$, such that a set $S_d \subseteq S$ of obstacles separates $s$ from $t$ if and only if $G[S_d]$ contains a cycle whose sum of labels is odd.使用分离障碍集的这种结构表征，我们获得以下算法结果。 在障碍物解释问题中，任务是在最多Q障碍物相交的平面中找到一条曲线。我们给出了$ 2.3146^qn^{o（1）} $算法用于障碍物的算法，在以前最著名的$ q^{o（q^3）} n^{o（q^3）} n^{o（1）} $ eiben and Lokshtanov（SocG'20）上有了显着改善。我们还获得了用于障碍物驱动的常数因子近似算法的替代证明，从而大大简化了Kumar等人的参数。 （苏打21）。 在广义点分离问题中，输入由障碍集组成，k点和p对的点a a的点a（s_1，t_1），...（s_p，t_p，t_p）$。 $ S_R $。我们获得$ 2^{o（p）} n^{o（k）} $ - 通用点分离问题的时间算法。这解决了Cabello和Giannopoulos（SOCG'13）的一个空缺问题，他们询问了这种特殊情况的存在算法的存在，其中$（s_1，t_1），...（s_p，t_p）$包含A。 n^{o（\ sqrt {k}）} $当障碍物是单位磁盘时，其中$ f（p，k）= 2^o（p）k^{o（k）} $，并表明，假设指数时间假设（ETH），我们的运行时间对我们的$ k $ of我们的algorithms of Algorithms Issencelys均为$ k $。
Suppose we are given a pair of points $s, t$ and a set $S$ of $n$ geometric objects in the plane, called obstacles. We show that in polynomial time one can construct an auxiliary (multi-)graph $G$ with vertex set $S$ and every edge labeled from $\{0, 1\}$, such that a set $S_d \subseteq S$ of obstacles separates $s$ from $t$ if and only if $G[S_d]$ contains a cycle whose sum of labels is odd. Using this structural characterization of separating sets of obstacles we obtain the following algorithmic results. In the Obstacle-Removal problem the task is to find a curve in the plane connecting s to t intersecting at most q obstacles. We give a $2.3146^qn^{O(1)}$ algorithm for Obstacle-Removal, significantly improving upon the previously best known $q^{O(q^3)} n^{O(1)}$ algorithm of Eiben and Lokshtanov (SoCG'20). We also obtain an alternative proof of a constant factor approximation algorithm for Obstacle-Removal, substantially simplifying the arguments of Kumar et al. (SODA'21). In the Generalized Points-Separation problem, the input consists of the set S of obstacles, a point set A of k points and p pairs $(s_1, t_1),... (s_p, t_p)$ of points from A. The task is to find a minimum subset $S_r \subseteq S$ such that for every $i$, every curve from $s_i$ to $t_i$ intersects at least one obstacle in $S_r$. We obtain $2^{O(p)} n^{O(k)}$-time algorithm for Generalized Points-Separation problem. This resolves an open problem of Cabello and Giannopoulos (SoCG'13), who asked about the existence of such an algorithm for the special case where $(s_1, t_1), ... (s_p, t_p)$ contains all the pairs of points in A. Finally, we improve the running time of our algorithm to $f(p,k) n^{O(\sqrt{k})}$ when the obstacles are unit disks, where $f(p,k) = 2^O(p) k^{O(k)}$, and show that, assuming the Exponential Time Hypothesis (ETH), the running time dependence on $k$ of our algorithms is essentially optimal.
