License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2022.52
URN: urn:nbn:de:0030-drops-160609
Go to the corresponding LIPIcs Volume Portal

Kumar, Neeraj ; Lokshtanov, Daniel ; Saurabh, Saket ; Suri, Subhash ; Xue, Jie

Point Separation and Obstacle Removal by Finding and Hitting Odd Cycles

LIPIcs-SoCG-2022-52.pdf (0.9 MB)


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.

BibTeX - Entry

  author =	{Kumar, Neeraj and Lokshtanov, Daniel and Saurabh, Saket and Suri, Subhash and Xue, Jie},
  title =	{{Point Separation and Obstacle Removal by Finding and Hitting Odd Cycles}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{52:1--52:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-160609},
  doi =		{10.4230/LIPIcs.SoCG.2022.52},
  annote =	{Keywords: points-separation, min color path, constraint removal, barrier resillience}

Keywords: points-separation, min color path, constraint removal, barrier resillience
Collection: 38th International Symposium on Computational Geometry (SoCG 2022)
Issue Date: 2022
Date of publication: 01.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI