A Colored Path Problem and Its Applications
A Colored Path Problem and Its Applications
复制标题
一个彩色路径问题及其应用
DOI：
10.1145/3396573
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Iyad A. Kanj
中科院分区：
文献类型：
--
作者：
E. Eiben;Iyad A. Kanj
给定一组障碍物和平面上的两点，两点之间是否有一条路径不穿过超过k个不同的障碍物？同样地，我们是否可以移除k个障碍物，使两个指定的点之间有一条无障碍的路径？这是一个基本的np难题，已经经历了大量的研究工作。这个问题可以表述和推广为如下的图问题：给定一个平面图G，其顶点由颜色集着色，两个指定的顶点s， t∈V(G), k∈N，在G中是否存在s-t路径，最多使用k种颜色？如果每个障碍都是连通的，则生成的图满足颜色连通性，即每种颜色都能引出连通子图。我们研究了上述图问题的复杂性和设计算法，并着眼于其几何应用。我们证明了一组硬度结果，其中一个结果表明颜色连通性对于固定参数可处理（FPT）算法的任何希望都是至关重要的。我们还表明，我们的硬度结果转化为几何实例的问题。然后我们将重点放在满足颜色连通性的图上。针对这一问题，我们设计了一个以k和图的树宽为参数化的FPT算法，并进一步推广了这一结果，得到了以k和路径长度为参数化的FPT算法。后一个结果暗示并解释了之前各种障碍物形状的FPT结果。
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 ∈ V(G), and k ∈ 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.
影响因子：
1.1
作者：
Hershberger, J.;Kumar, N.;Suri, S.
通讯作者：
Suri, S.