In the barrier resilience problem (introduced by Kumar et al., Wireless Networks 2007), we are given a collection of regions of the plane, acting as obstacles, and we would like to remove the minimum number of regions...
详细信息
In the barrier resilience problem (introduced by Kumar et al., Wireless Networks 2007), we are given a collection of regions of the plane, acting as obstacles, and we would like to remove the minimum number of regions so that two fixed points can be connected without crossing any region. In this paper, we show that the problem is NP-hard when the collection only contains fat regions with bounded ply Delta (even when they are axis aligned rectangles of aspect ratio 1 : (1 + epsilon)). We also show that the problem is fixed parameter tractable (FPT) for unit disks and for similarly-sized beta-fat regions with bounded ply Delta and 0(1) pairwise boundary intersections. We then use our FPT algorithm to construct an (1 + epsilon)-approximation algorithm that runs in O(2f((Delta,epsilon,beta))n(5)) time, where f is an element of O (Delta(4)beta(8)/epsilon(4) log(beta Delta/epsilon)). (C) 2018 Elsevier B.V. All rights reserved.
Given a set of obstacles and two points in the plane, is there a path between the two points that does not cross more than k different obstacles? Equivalently, can we remove k obstacles so that there is an obstacle-fr...
详细信息
Given a set of obstacles and two points in the plane, is there a path between the two points that does not cross more than k different obstacles? Equivalently, can we remove k obstacles so that there is an obstacle-free path between the two designated points? This is a fundamental NP-hard problem that has undergone a tremendous amount of research work. The problem can be formulated and generalized into the following graph problem: Given a planar graph G whose vertices are colored by color sets, two designated vertices s, t is an element of V(G), and k is an element of N, is there an s-t path in G that uses at most k colors? If each obstacle is connected, then the resulting graph satisfies the color-connectivity property, namely that each color induces a connected subgraph. We study the complexity and design algorithms for the above graph problem with an eye on its geometric applications. We prove a set of hardness results, including a result showing that the color-connectivity property is crucial for any hope for fixed-parameter tractable (FPT) algorithms. We also show that our hardness results translate to the geometric instances of the problem. We then focus on graphs satisfying the color-connectivity property. We design an FPT algorithm for this problem parameterized by both k and the treewidth of the graph and extend this result further to obtain an FPT algorithm for the parameterization by both k and the length of the path. The latter result implies and explains previous FPT results for various obstacle shapes.
暂无评论