2026-08-12T09:16:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16060 2024-03-06T10:56:51Z ddc:004 open_access

Point Separation and Obstacle Removal by Finding and Hitting Odd Cycles Kumar, Neeraj Lokshtanov, Daniel Saurabh, Saket Suri, Subhash Xue, Jie points-separation min color path constraint removal barrier resillience Suppose we are given a pair of points s, t and a set 𝒮 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 𝒮 and every edge labeled from {0, 1}, such that a set 𝒮_d ⊆ 𝒮 of obstacles separates s from t if and only if G[𝒮_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^q n^{O(1)} algorithm for Obstacle-removal, significantly improving upon the previously best known q^{O(q³)} 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 input consists of the set 𝒮 of obstacles, a point set A of k points and p pairs (s₁, t₁), … (s_p, t_p) of points from A. The task is to find a minimum subset 𝒮_r ⊆ 𝒮 such that for every i, every curve from s_i to t_i intersects at least one obstacle in 𝒮_r. We obtain 2^{O(p)} n^{O(k)}-time algorithm for Generalized Points-separation. 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₁, t₁), … (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(√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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Neeraj Kumar and Daniel Lokshtanov and Saket Saurabh and Subhash Suri and Jie Xue 2022 Is Part Of LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2022.52 urn:nbn:de:0030-drops-160609 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.52 eng https://creativecommons.org/licenses/by/4.0/legalcode